ZH
RU
EN
ES
FR
DE
PT
AR
HI
根据一组距离重建凸多边形
Python
Hard
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