POINTS

  • Точки
    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