Задача №1996. Ломаная
На плоскости даны \(N\) точек. Требуется провести через все эти точки замкнутую несамопересекающуюся ломаную. (Ломаную назовём несамопересекающейся, если каждый её отрезок не имеет с другими отрезками общих точек, за исключением одной общей точки — одного из концов — с каждым из своих соседей.)
В первой строке входного файла содержится натуральное число \(N\) (\(3\le N\le10^4\)). В следующих \(N\) строках содержатся пары чисел \((x_i,y_i)\) — координаты соответствующих точек
Если решения не существует, выведите единственное число \(-1\). Иначе выведите \(N\) чисел (перестановку чисел \(1,2,\ldots,N\)) — номера точек в порядке их обхода ломаной. Если существует несколько решений (или несколько способов задания одной ломаной), выведите любое.
Комментарий к примеру тестов.
В качестве ответа не подходят, например, следующие ломаные:
3 2 9 8 1 7 6 10 5 4
1 2 9 8 7 6 3 4 5 10
1 2 3 4 5 6 7 8 9 10
10 0 1 1 2 -1 3 -2 4 -2 2 0 0 2 0 3 1 2 3 -3 3 -2 2
0