Задача на Паскаль: по заданному множеству N точек построить N-угольник

[Dragon65]

Имеется робот,который,глядя на множество точек, легко определяет их координаты в координатном множестве, необходимо составить программу,которая учит робота соединять точки так, чтобы получился ЛЮБОЙ N-угольник,без самопересечний и "усов".
На вход программе подается число N(от 3 до 1000000) всех точек.
И координаты в N строчках всех точек x и y (от -1000 до 1000)

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

Пример:
Input
7(кол-во точек)
2 3 (x_y первой точки)
3 2
5 1
5 3
6 2
4 2
4 3
Output
3 5 4 7 6 1 2
На мой взгляд это сложная задача, можете подсказать как решать и её вообще можно решить на языке Pascal?
Я думал создать цикл,в котором анализируется принадлежность каждой точки только к вершинам двух прямых,но учитывая количество точек это как то неразумно вроде... -или без этого анализа не обойтись?
Сколько точек, столько и сторон многоугольнике,думаю в конце можно поставить условие чтобы сторон было столько же сколько точек (N)

[Poma][a]

Дайте ссыль на задачу..

Я бы расчитывал по формуле угол и ходил по нему..

[Аватар]

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

[Poma][a]

Кстати, если строить правильные N-угольники? На окружности рисовать окружности радиусом 2PiR/N.. Сначала из произвольной точки, далее из точки пересечения этой окружности с большой..

[Аватар]

Правильные слабо будет построить по произвольным точкам. Или о чем-то другом речь идет?

[Poma][a]

Правильные слабо будет построить по произвольным точкам. Или о чем-то другом речь идет?

Ну да.. кто-то надеясь на телепатор не стал читать условие.. Простите..

[Dragon65]

Добавить точку внутри выпуклой оболочки, это интересно, но как узнаем что эта точка именно внутри оболочки? допустим если точек максимум,10^6(миллион), нужно всё равно чтобы N-угольник получился.
Если выбирать эту точку со случайными координатами наверно должно быть условие, когда эта точка лежит не внутри оболочки, а произойдет самопересечение,это можно как-то учесть?

Может быть очень много случаев расположений N-угольника,т.к. сказано что он любой, и в некоторых случаев, соединяя заданные точки с внутренней Вашей точкой, произойдет пересечение с самой фигурой,это влияет на что-нибудь?

[Аватар]

Про выпуклую оболочку я загнул, можно в любом месте. Главное, что бы не совпадала с точкой из множества. Про сортированные углы - на бумаге из этой точки провелись бы лучи во все остальные точки. На некоторых из них возможно попадут точки. И начиная с конечной точки любого луча по часовой стрелке соединяем отрезком с самой ближней к нашей лишней точке точку на соседнем луче и т.д. Хоть триллионы точек. Самопересечений не предвидится

соединяя заданные точки с внутренней Вашей точкой

Эта левая точка вообще-то ни с чем и не будет соединяться в конечном счете, а нужна только для алгоритма

[Dragon65]

действительно,т.е. из 1 любой точки, не совпадающей с точкой множества выходит бесконечное множество различных лучей,на некоторые точно попадут всё наши точки и их нужно просто соединять.
Но этих лучей будет много,в случае большого числа точек(N)-это каждый луч придется задавать и смотреть углы между выходящими из "пробной" точки? -Соединять придется те точки, у которых между лучами наименьший угол-скалярное произведение?

"пробную" точку мы задаем сами далее в цикле от 1 до N нужно будет брать модули двух лучей и разность координат x и y точек, cos(a)=(ab)/(|a||b|)-для первых 2 точек,не факт ,что ещё их придется соединять,далее определяем косинус м/у первой и 3-ей точкой, м/у 1 и 4-ой,м/у 1 и 5-ой и т.д. до N и при этом сравниваем их.

Но чтобы программа в цикле for i:=1 to N do...
под 1 понимала координаты первой точки допустим, нужен массив?
Вывести придется N цифр в правильном порядке, если N очень большое, то N переменных завести не получится,как тут быть?

[Аватар]

из 1 любой точки, не совпадающей с точкой множества выходит бесконечное множество различных лучей

Бесконечное и не нужно, а нужны именно конкретные лучи. Да, и немного подумал, все таки произвольная точка не прокатит, ибо будет проблема соединения начала и конца. Но и выпуклая оболочка не нужна. А нужна точка, координаты которой попадают в MinMax предложенного множества точек

чтобы программа в цикле

В одном цикле рассчитываем углы. Дальше примитивная сортировка и в цикле выдача номеров точек. Ну и точку придумать с проверкой на не совпадения с предложенными, тоже цикл и возможно вложенный в другой