Мне даны кординаты n точек на плоскости. Как узнать, являются ли они вершинами n-угольника?

Question

Спасибо.

Answer 1

Проверить каждую тройку точек на предмет лежат ли они на одной прямой. Если ответ отрицательный, все n точек являются вершинами n-угольника.
Или вас интересует конкретно выпуклый многоугольник?

Answer 2

Это зависит от того, имешь ли ты в виду правильный многоугольник, любой многоугольник или любой не самопересекающийся многоугольник. Если ты имешь в виду любой многоугольник, то ты всегда можешь создать не самопересекающийся многоугольник из заданного набора точек. Найти минимальную - это пример задачи коммивояжера.

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