如何通过点间距离确定直线上多个点的排列顺序

核心利用共线点的距离特性实现即可，步骤如下：

• 步骤1：解析输入构建距离映射
  先把输入的文本内容解析成字典形式的距离查询表，比如dist['A']['B'] = 57，同时提取所有不重复的点存到列表里，示例里就是['A','B','C']。
• 步骤2：找到直线的两个端点
  共线的所有点里，距离最远的两个点就是直线的左右两个端点。遍历所有点对计算距离，找到距离最大的那两个点，记为start和end，示例里最大距离是100，对应的两个点就是B和C。
• 步骤3：按距起点的距离排序得到最终序列
  把所有的点，按照到start的距离从小到大排序，得到的序列就是直线上从start到end的先后排列顺序。示例里各点到B的距离分别是B:0、A:57、C:100，排序后就是['B','A','C']，和预期输出完全一致。

可选校验逻辑 #

如果需要提前校验输入的距离矩阵是否对应共线的点，可以加一层验证：

任选三个点x、y、z，检查是否满足三个距离中最大值等于另外两个值的和，如果所有三元组都满足这个条件，说明所有点确实共线，排序结果有效。

简易伪代码参考 #

# 解析输入
dist = {}
points = set()
with open('input.txt', 'r') as f:
    for line in f:
        a, b, d = line.strip().split(',')
        d = int(d)
        if a not in dist:
            dist[a] = {}
        dist[a][b] = d
        points.add(a)
        points.add(b)
points = list(points)

# 找端点
max_d = -1
start = None
end = None
for i in range(len(points)):
    for j in range(i+1, len(points)):
        a = points[i]
        b = points[j]
        if dist[a][b] > max_d:
            max_d = dist[a][b]
            start = a
            end = b

# 排序
points.sort(key=lambda x: dist[start][x])
print(points)

内容的提问来源于stack exchange，提问作者uam2020