Вершины в порядке обхода по часовой стрелке - 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"); }
Объяснение кода листинга программы
- Включаются необходимые заголовочные файлы
- Объявляется структура
Xy
для представления вершин - Инициализируется переменная
xy_origin
, которая содержит координаты начальной вершины - Определяется функция
cmp_polar_angle
для сравнения вершин по углу относительно начальной вершины - В функции
main
инициализируется массивpoly
с координатами вершин - Вычисляется количество вершин в массиве
poly
и сохраняется в переменнуюn
- Находится вершина с минимальной y-координатой (это будет начальная вершина)
- Сортируются вершины массива
poly
относительно начальной вершины с использованием функцииqsort
и пользовательской функцииcmp_polar_angle
- Выводятся координаты каждой вершины массива
poly
через пробел - Программа завершается
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д