RU
EN
ES
ZH
FR
DE
PT
AR
HI
Реконструкция выпуклого многоугольника по набору расстояний
Python
Сложный
math
Задача «Реконструкция выпуклого многоугольника по набору расстояний»
Дан набор из N точек на плоскости, образующих выпуклый многоугольник в порядке обхода. Известны все попарные расстояния между вершинами, но порядок следования точек неизвестен. Необходимо восстановить исходный порядок вершин (их номера от 1 до N) так, чтобы полученный многоугольник был выпуклым и имел те же попарные расстояния. Гарантируется, что решение единственно. Выведите номера вершин в порядке обхода по часовой стрелке, начиная с вершины с минимальным номером.
Формат ввода
Первая строка содержит целое число N (3 ≤ N ≤ 100). Следующие N строк содержат по N целых чисел — матрицу расстояний A, где A[i][j] = A[j][i] — квадрат евклидова расстояния между i-й и j-й вершиной (0 ≤ A[i][j] ≤ 10^9). Диагональные элементы равны 0. Матрица симметрична.
Формат вывода
Выведите N чисел — номера вершин в порядке обхода по часовой стрелке, начиная с минимального номера. Если восстановить многоугольник невозможно, выведите -1.
Примеры
Пример 1
ВВОД
4
0 1 4 1
1 0 1 4
4 1 0 1
1 4 1 0
ВЫВОД
1 2 3 4
Пример 2
ВВОД
5
0 2 5 5 2
2 0 2 5 5
5 2 0 2 5
5 5 2 0 2
2 5 5 2 0
ВЫВОД
1 2 3 4 5
Пример 3
ВВОД
5
1 2 3 4 5
5
3 4 5 6 7
ВЫВОД
main.py