EN
RU
ES
ZH
FR
DE
PT
AR
HI
Reconstruction of a convex polygon from a set of distances
Python
Hard
math
Task «Reconstruction of a convex polygon from a set of distances»
Given a set of N points on a plane that form a convex polygon in traversal order. All pairwise distances between the vertices are known, but the order of the points is unknown. It is necessary to restore the original order of the vertices (their numbers from 1 to N) so that the resulting polygon is convex and has the same pairwise distances. It is guaranteed that the solution is unique. Output the vertex numbers in clockwise traversal order, starting from the vertex with the smallest number.
Input Format
The first line contains an integer N (3 ≤ N ≤ 100). The next N lines contain N integers each — the distance matrix A, where A[i][j] = A[j][i] is the square of the Euclidean distance between the i-th and j-th vertex (0 ≤ A[i][j] ≤ 10^9). The diagonal elements are 0. The matrix is symmetric.
Output Format
Output N numbers — the vertex numbers in clockwise order, starting from the minimum number. If it is impossible to reconstruct the polygon, output -1.
Examples
Example 1
INPUT
4
0 1 4 1
1 0 1 4
4 1 0 1
1 4 1 0
OUTPUT
1 2 3 4
Example 2
INPUT
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
OUTPUT
1 2 3 4 5
Example 3
INPUT
5
1 2 3 4 5
5
3 4 5 6 7
OUTPUT
main.py