Вершины в порядке обхода по часовой стрелке - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Выпуклый многоугольник на плоскости задан своими вершинами, расположенными в произвольном порядке. Расположить вершины в порядке обхода по часовой стрелке. Помогите с заданием пожалуйста.

Решение задачи: «Вершины в порядке обхода по часовой стрелке»

textual
Листинг программы
#include <stdlib.h>
#include <stdio.h>
 
typedef struct Xy
{
  int x, y;
} Xy;
 
static const Xy *xy_origin;
 
int cmp_polar_angle(const void *p1, const void *p2)
{
  const Xy *xy1 = p1, *xy2 = p2;
 
  Xy 
    origin_xy1 = { xy1->x - xy_origin->x, xy1->y - xy_origin->y },
    origin_xy2 = { xy2->x - xy_origin->x, xy2->y - xy_origin->y };
 
  long long area = 
    (long long) origin_xy1.x * origin_xy2.y - 
    (long long) origin_xy1.y * origin_xy2.x;
 
  return (area > 0) - (area < 0);
}
 
int main()
{
  Xy poly[] = { { 0, 0 }, { 2, 5 },  { -3, -1 }, { 0, 9 }, { -5, 3 } };
  const unsigned n = sizeof poly / sizeof *poly;
 
  /* Find min-y point */
 
  for (unsigned i = 1; i < n; ++i)
    if (poly[i].y < poly[0].y)
    {
      Xy temp = poly[0];
      poly[0] = poly[i];
      poly[i] = temp;
    }
 
  /* Sort the vertices */
 
  xy_origin = &poly[0];
  qsort(poly + 1, n - 1, sizeof *poly, cmp_polar_angle);
 
  /* Done */
 
  for (unsigned i = 0; i < n; ++i)
    printf("{ %d, %d } ", poly[i].x, poly[i].y);
  printf("\n");
}

Объяснение кода листинга программы

  1. Включаются необходимые заголовочные файлы
  2. Объявляется структура Xy для представления вершин
  3. Инициализируется переменная xy_origin, которая содержит координаты начальной вершины
  4. Определяется функция cmp_polar_angle для сравнения вершин по углу относительно начальной вершины
  5. В функции main инициализируется массив poly с координатами вершин
  6. Вычисляется количество вершин в массиве poly и сохраняется в переменную n
  7. Находится вершина с минимальной y-координатой (это будет начальная вершина)
  8. Сортируются вершины массива poly относительно начальной вершины с использованием функции qsort и пользовательской функции cmp_polar_angle
  9. Выводятся координаты каждой вершины массива poly через пробел
  10. Программа завершается

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.933 из 5
Похожие ответы