PT
RU
EN
ES
ZH
FR
DE
AR
HI
Reconstrução de um polígono convexo a partir de um conjunto de distâncias
Python
Hard
math
Tarefa «Reconstrução de um polígono convexo a partir de um conjunto de distâncias»
Dado um conjunto de N pontos no plano, formando um polígono convexo na ordem de percurso. Todas as distâncias aos pares entre os vértices são conhecidas, mas a ordem dos pontos é desconhecida. É necessário reconstruir a ordem original dos vértices (seus números de 1 a N) de modo que o polígono resultante seja convexo e tenha as mesmas distâncias aos pares. Garante-se que a solução é única. Imprima os números dos vértices na ordem de percurso no sentido horário, começando pelo vértice de menor número.
Formato de Entrada
A primeira linha contém um inteiro N (3 ≤ N ≤ 100). As próximas N linhas contêm N inteiros cada — a matriz de distâncias A, onde A[i][j] = A[j][i] é o quadrado da distância euclidiana entre o i-ésimo e o j-ésimo vértice (0 ≤ A[i][j] ≤ 10^9). Os elementos da diagonal são 0. A matriz é simétrica.
Formato de Saída
Imprima N números — os números dos vértices na ordem de percurso no sentido horário, começando pelo menor número. Se for impossível reconstruir o polígono, imprima -1.
Exemplos
Exemplo 1
ENTRADA
4
0 1 4 1
1 0 1 4
4 1 0 1
1 4 1 0
SAÍDA
1 2 3 4
Exemplo 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
SAÍDA
1 2 3 4 5
Exemplo 3
ENTRADA
5
1 2 3 4 5
5
3 4 5 6 7
SAÍDA
main.py