 POINTS
| Задача На плоскости дано N точек своими координатами. Необходимо на базе всех этих точек, (как на вершинах) построить замкнутую не самопересекающуюся ломаную.  (Рис.1) является примером замкнутой не самопересекающейся ломаной. (Рис.2) - это замкнутая, но самопересекающаяся ломаная (Рис.3) - это незамкнутая и не самопересекающаяся ломаная. Технические условия: Входные данные: файл INPUT.TXT В первой строке число N Далее N строк вводятся через пробел координаты каждой точке - Xi и Yi Выходные данные: файл OUTPUT.TXT Если замкнутую не самопересекающуюся ломаную построить нельзя, то в первой строке должно быть слово No, иначе слово Yes. Если решение найдено, то далее должно находится через пробел N+1 чисел - номера точек в порядке обхода ломаной, причем номер первой вершина выводится вначале и в конце. Ограничения и уточнения: 3<=N<=3000 -1000<=Xi, Yi<=1000 Время на тест: 1 секунда (для Athlon XP 1800+) Координаты точек вводятся с точностью 0.01 Если существует несколько решений, то достаточно выдать одно из них. Каждая точка имеет свой номер, причем номера точек соответствуют порядку их ввода. Примерs: INPUT.TXT | | OUTPUT.TXT | 11 5 3 0 1 8 0 4 1 2 6 8 3 2 3 6 5 4.5 6 7.5 8 4 5 | | YES 4 7 2 5 11 9 10 8 6 3 1 4 | | | | INPUT.TXT | | OUTPUT.TXT | 5 -2 -2 -1 -1 0 0 1 1 2 2 | | NO | |
---|