平面上两点最近距离：笛卡尔积要减半
LeetCode 612 · 自连接、笛卡尔积、减少重复计算
面试怎么回答
点两两比较需要自连接，我会加方向条件让每对只算一次，比如 (p1.x, p1.y) < (p2.x, p2.y) 的字典序比较，再对距离平方取 MIN，最后开方并保留两位。点很多时笛卡尔积是 O(n²)，真实场景要先按网格分桶再比较。
先把这段讲顺；面试官追问时，再展开下面的原理和细节。
详细讲解
题意
点表保存了平面上若干个互不重合的点的坐标。求任意两点之间的最短距离，保留两位小数。
表结构
- point_2d：x、y；(x, y) 为主键
思路
两两比较只能自连接。第一种写法连接条件是「两点不同」，每对点会算两次（A-B 和 B-A）。第二种写法给连接加了方向约束，让每对点只算一次。另外开方是单调的，可以先对距离平方取最小值，最后只开一次方。
参考解法
写法 1：所有不同点两两配对
SELECT
ROUND(SQRT(MIN((POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2)))), 2) AS shortest
FROM
point_2d p1
JOIN
point_2d p2 ON p1.x != p2.x OR p1.y != p2.y写法 2：加方向约束，每对点只比较一次
SELECT
ROUND(SQRT(MIN((POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2)))),2) AS shortest
FROM
point_2d p1
JOIN
point_2d p2 ON (p1.x <= p2.x AND p1.y < p2.y)
OR (p1.x <= p2.x AND p1.y > p2.y)
OR (p1.x < p2.x AND p1.y = p2.y)易错点
- 连接条件写成
p1.x != p2.x AND p1.y != p2.y会漏掉 x 或 y 相同的点对。 - SQRT 放在 MIN 外面只算一次；放在里面每对都要开方。