ES
RU
EN
ZH
FR
DE
PT
AR
HI
Reconstrucción de un polígono convexo a partir de un conjunto de distancias
Python
Hard
math
Tarea «Reconstrucción de un polígono convexo a partir de un conjunto de distancias»
Se da un conjunto de N puntos en el plano que forman un polígono convexo en orden de recorrido. Se conocen todas las distancias por pares entre los vértices, pero se desconoce el orden de los puntos. Es necesario reconstruir el orden original de los vértices (sus números del 1 al N) de modo que el polígono resultante sea convexo y tenga las mismas distancias por pares. Se garantiza que la solución es única. Imprima los números de los vértices en orden de recorrido en el sentido de las agujas del reloj, comenzando por el vértice con el número más pequeño.
Formato de entrada
La primera línea contiene un número entero N (3 ≤ N ≤ 100). Las siguientes N líneas contienen N números enteros cada una — la matriz de distancias A, donde A[i][j] = A[j][i] es el cuadrado de la distancia euclidiana entre el i-ésimo y j-ésimo vértice (0 ≤ A[i][j] ≤ 10^9). Los elementos de la diagonal son iguales a 0. La matriz es simétrica.
Formato de salida
Imprima N números — los números de los vértices en orden de recorrido en el sentido de las agujas del reloj, comenzando por el número más pequeño. Si no es posible reconstruir el polígono, imprima -1.
Ejemplos
Ejemplo 1
ENTRADA
4
0 1 4 1
1 0 1 4
4 1 0 1
1 4 1 0
SALIDA
1 2 3 4
Ejemplo 2
ENTRADA
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
SALIDA
1 2 3 4 5
Ejemplo 3
ENTRADA
5
1 2 3 4 5
5
3 4 5 6 7
SALIDA
main.py