FR
RU
EN
ES
ZH
DE
PT
AR
HI
Reconstruction d’un polygone convexe à partir d’un ensemble de distances
Python
Hard
math
Tâche «Reconstruction d’un polygone convexe à partir d’un ensemble de distances»
Un ensemble de N points dans le plan, formant un polygone convexe dans l’ordre de parcours, est donné. Toutes les distances deux à deux entre les sommets sont connues, mais l’ordre des points est inconnu. Il faut reconstituer l’ordre original des sommets (leurs numéros de 1 à N) de sorte que le polygone obtenu soit convexe et ait les mêmes distances deux à deux. La solution est garantie unique. Affichez les numéros des sommets dans l’ordre de parcours dans le sens horaire, en commençant par le sommet de plus petit numéro.
Format d\ entrée
La première ligne contient un entier N (3 ≤ N ≤ 100). Les N lignes suivantes contiennent N entiers chacune — la matrice des distances A, où A[i][j] = A[j][i] est le carré de la distance euclidienne entre le i-ème et le j-ème sommet (0 ≤ A[i][j] ≤ 10^9). Les éléments diagonaux sont nuls. La matrice est symétrique.
Format de sortie
Affichez N nombres — les numéros des sommets dans l’ordre de parcours dans le sens horaire, en commençant par le plus petit numéro. S’il est impossible de reconstituer le polygone, affichez -1.
Exemples
Exemple 1
ENTRÉE
4
0 1 4 1
1 0 1 4
4 1 0 1
1 4 1 0
SORTIE
1 2 3 4
Exemple 2
ENTRÉE
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
SORTIE
1 2 3 4 5
Exemple 3
ENTRÉE
5
1 2 3 4 5
5
3 4 5 6 7
SORTIE
main.py