更新题目 593. Valid Square
题目 lc593 · 修改（rev 7） · · 2026-10-27 00:33
body
@@ -1,11 +1,13 @@ ## TL;DR -看过全文之后，考前用这一节过一遍。每条都指向正文里讲它的那一节。 - -- **做法**（思路第 3 节、代码一节）：算出 4 个点两两之间 6 个距离的平方，从小到大排好。是正方形，当且仅当最小的 4 个相等且大于 0，最大的 2 个相等，而且最大的那个恰好是最小的 2 倍。全程整数运算，没有浮点误差。 -- **为什么这几条就够**（思路第 5 节）：两条最长的线段如果没有公共端点，它们就是两条对角线，另外两个点只有一种摆法，拼出来正好是正方形，「2 倍」在这种情况下自动成立。如果有公共端点，图形是一个等边三角形加一个点（风筝形），长短距离平方之比是 2 ± √3，不是 2，只有「2 倍」这一条能挡住它。「边长大于 0」这一条只为挡住「4 个点完全重合」。 -- **三个容易踩的坑**（思路第 2、4、5 节）：把输入顺序当成绕一圈的顺序，点给乱了就漏判，有重合点还会误判。用真实距离去比「对角线 = 边 × √2」，45° 斜放的正方形会因为浮点误差判成 False。只查「最小 4 个相等、最大 2 个相等」而不查 2 倍，整数坐标下不会出错，浮点坐标会把风筝形判成正方形。 -- **开写前要问**（题目一节的表）：能不能斜着放，坐标是不是整数，重合点算不算，点按什么顺序给。 -- **接下来的追问**是「一堆点里有多少个正方形」，要从 O(n⁴) 优化到 O(n²)，单独一页：[[q:everpure-count-squares]]。它的 O(n²) 做法用的是思路第 6 节「已知一条对角线，推出另外两个角」。 +- 4 个点两两间 6 个距离的平方排好序，最小 4 个相等且大于 0、最大 2 个相等、最大是最小的 2 倍，就是正方形，全程整数没有浮点误差（思路第 3 节、代码一节）。 +- 两条最长线段没有公共端点时就是对角线，另外两点只有一种摆法，正好拼成正方形，「2 倍」自动成立（思路第 5 节）。 +- 有公共端点时是等边三角形加一个点（风筝形），长短距离平方之比是 $2 \pm \sqrt{3}$，不是 2，只有「2 倍」能挡住它（思路第 5 节）。 +- 「边长大于 0」只为挡住 4 个点完全重合（思路第 5 节）。 +- 把输入顺序当成绕一圈的顺序，点给乱了会漏判，有重合点还会误判（思路第 2 节）。 +- 用真实距离比 $\sqrt{2}$ 倍，45° 斜放的正方形因浮点误差判成 False（思路第 4 节）。 +- 不查 2 倍，整数坐标下不出错，浮点坐标会把风筝形判成正方形（思路第 5 节）。 +- 开写前问：能否斜放、坐标是否整数、重合点算不算、点按什么顺序给（题目一节的表）。 +- 追问是数一堆点里的正方形，从 $O(n^4)$ 优化到 $O(n^2)$，单独一页 [[q:everpure-count-squares]]，其 $O(n^2)$ 做法靠思路第 6 节「已知一条对角线，推出另外两个角」。 ## 题目 @@ -13,5 +15,5 @@ 面试官口头给一句话：平面上有 4 个点，每个点是一对坐标 (x, y)，判断这 4 个点能不能组成一个正方形。面经里记下来的题面只有这一句，没有函数签名，没有指定语言，也没说坐标是整数还是小数、点按什么顺序给。下面按 LeetCode 593 的签名写：函数 `valid_square(p1, p2, p3, p4)` 接收 4 个点，每个点是一个 `[x, y]` 列表，返回 True 或 False。 -[LeetCode 593](https://leetcode.com/problems/valid-square/) 的约定是：坐标是整数，绝对值不超过 10⁴。点的顺序任意。正方形可以斜着放。正方形要求四条边等长且长度为正、四个角都是 90°，所以 4 个点里有重合的就返回 False。这些是 LeetCode 的规定，面经里的面试官有没有这么说，帖子里没写，开写前要自己问（见下面的表）。 +[LeetCode 593](https://leetcode.com/problems/valid-square/) 的约定是：坐标是整数，绝对值不超过 $10^4$。点的顺序任意。正方形可以斜着放。正方形要求四条边等长且长度为正、四个角都是 90°，所以 4 个点里有重合的就返回 False。这些是 LeetCode 的规定，面经里的面试官有没有这么说，帖子里没写，开写前要自己问（见下面的表）。 几个具体例子： @@ -20,6 +22,6 @@ | --- | --- | --- | | `[0,0] [1,1] [1,0] [0,1]` | True | 边长 1 的正方形，点的顺序是交叉给的 | -| `[0,0] [2,1] [1,3] [-1,2]` | True | 斜着放的正方形，边长 √5 | -| `[0,0] [2,1] [3,3] [1,2]` | False | 菱形（rhombus，四条边相等的四边形）：四条边都是 √5，两条对角线一长一短（√18 和 √2），角不是直角，所以不是正方形 | +| `[0,0] [2,1] [1,3] [-1,2]` | True | 斜着放的正方形，边长 $\sqrt{5}$ | +| `[0,0] [2,1] [3,3] [1,2]` | False | 菱形（rhombus，四条边相等的四边形）：四条边都是 $\sqrt{5}$，两条对角线一长一短（$\sqrt{18}$ 和 $\sqrt{2}$），角不是直角，所以不是正方形 | | `[0,0] [1,1] [1,0] [0,12]` | False | 随便放的 4 个点，6 个距离平方是 1、1、2、122、144、145，谈不上什么形状 | | `[0,0] [0,0] [0,0] [0,0]` | False | 4 个点重合，边长是 0 | @@ -41,7 +43,7 @@ 4 个点判正方形在 [[c:everpure]]（原 Pure Storage）的面经里最早见于 2016 年，到 2026 年还在考，多数在电话面试，也有出现在现场面试（onsite）代码轮的。问法基本固定：面试官先口头给「4 个点判正方形」，候选人写完，记了 follow-up 的几篇接下来都是「给一堆点，能组成多少个正方形」，再要求一步步优化（[[q:everpure-count-squares]]）。 -写得最细的是 2017 年的一篇[一亩三分地帖子](https://www.1point3acres.com/home/thread/298316)。发帖人两轮电话面试都考了这道题和 Fire Event（[[q:everpure-fire-event]]），他记下的 follow-up 是给 n 个点问能组成多少个正方形，先写 O(n⁴)，再改进到 O(n³)，最后到 O(n²)。他还整理了一份题单，说电话面试一般从前五道里出两道，现场面试很可能也从这份题单出。评论区里他补了两点：4 个点他用的是「四条边相等，对角线相等」，这句话没说哪几对点是边，照字面写会出错（思路第 2 节）。数正方形只要讲清思路，不用写代码。另外有人在评论里问正方形能不能斜着放，能看到的回复里没人回答。 - -后来的面经补了两处细节。2025-12 的一位发帖人说面试官明确要求从 O(n⁴) 到 O(n³) 再到 O(n²)。2026-04 的一位发帖人用 6 个距离判断：4 个相等是边，2 个相等是对角线，对角线是边的 √2 倍。这个思路对，但帖子没说比的是距离还是距离的平方。照字面用浮点数比「√2 倍」，45° 斜放的正方形会判错（思路第 4 节）。 +写得最细的是 2017 年的一篇[一亩三分地帖子](https://www.1point3acres.com/home/thread/298316)。发帖人两轮电话面试都考了这道题和 Fire Event（[[q:everpure-fire-event]]），他记下的 follow-up 是给 n 个点问能组成多少个正方形，先写 $O(n^4)$，再改进到 $O(n^3)$，最后到 $O(n^2)$。他还整理了一份题单，说电话面试一般从前五道里出两道，现场面试很可能也从这份题单出。评论区里他补了两点：4 个点他用的是「四条边相等，对角线相等」，这句话没说哪几对点是边，照字面写会出错（思路第 2 节）。数正方形只要讲清思路，不用写代码。另外有人在评论里问正方形能不能斜着放，能看到的回复里没人回答。 + +后来的面经补了两处细节。2025-12 的一位发帖人说面试官明确要求从 $O(n^4)$ 到 $O(n^3)$ 再到 $O(n^2)$。2026-04 的一位发帖人用 6 个距离判断：4 个相等是边，2 个相等是对角线，对角线是边的 $\sqrt{2}$ 倍。这个思路对，但帖子没说比的是距离还是距离的平方。照字面用浮点数比「$\sqrt{2}$ 倍」，45° 斜放的正方形会判错（思路第 4 节）。 写了结果的几篇都是被拒，但能看到的记录里没有一篇把原因归到这道题，也没有人说在 4 个点这一问上卡住。所以这一问的目标是稳：几分钟写对，顺序、重合点、浮点数三处不留漏洞，把时间留给数正方形。面经里没人说被追问过「为什么这几条就够」，但这是最自然的追问，思路第 5 节要能当场讲出来【推断】。 @@ -53,7 +55,7 @@ 正方形（square）是四条边等长、四个角都是直角的四边形。把 4 个点按绕一圈的顺序叫 A、B、C、D，那么 AB、BC、CD、DA 是四条边，AC 和 BD 是两条对角线（diagonal），也就是连接不相邻两个角的线段。 -后面会反复用到一个几何事实：勾股定理（Pythagorean theorem），直角三角形里两条直角边的平方和等于斜边的平方。在正方形里，任意两条相邻的边和一条对角线组成一个直角三角形，所以「对角线² = 边² + 边² = 2 × 边²」，即对角线是边长的 √2 倍。 - -还有一个实现上的选择：**比较距离的平方（squared distance），不比较距离本身**。两点 (x₁, y₁)、(x₂, y₂) 的距离是 √((x₁−x₂)² + (y₁−y₂)²)，开根号以后一般是无理数，只能用浮点数近似。而距离的平方 (x₁−x₂)² + (y₁−y₂)² 在整数坐标下仍然是整数，可以用 `==` 精确比较。距离越长，平方也越大，所以比较平方和比较距离是一回事。 +后面会反复用到一个几何事实：勾股定理（Pythagorean theorem），直角三角形里两条直角边的平方和等于斜边的平方。在正方形里，任意两条相邻的边和一条对角线组成一个直角三角形，所以「$\text{对角线}^2 = \text{边}^2 + \text{边}^2 = 2 \times \text{边}^2$」，即对角线是边长的 $\sqrt{2}$ 倍。 + +还有一个实现上的选择：**比较距离的平方（squared distance），不比较距离本身**。两点 $(x_1, y_1)$、$(x_2, y_2)$ 的距离是 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$，开根号以后一般是无理数，只能用浮点数近似。而距离的平方 $(x_1 - x_2)^2 + (y_1 - y_2)^2$ 在整数坐标下仍然是整数，可以用 `==` 精确比较。距离越长，平方也越大，所以比较平方和比较距离是一回事。 ### 2. 按输入顺序判断为什么不行 @@ -79,5 +81,5 @@ ### 3. 不管顺序：把 6 个距离排序 -从 4 个点里选 2 个，有 C(4, 2) = 6 种选法，每一对算一个距离平方。如果这 4 个点是边长平方为 s 的正方形，这 6 个值里有 4 个是边，都等于 s。2 个是对角线，按勾股定理都等于 2s。排好序就是： +从 4 个点里选 2 个，有 $C(4, 2) = 6$ 种选法，每一对算一个距离平方。如果这 4 个点是边长平方为 s 的正方形，这 6 个值里有 4 个是边，都等于 s。2 个是对角线，按勾股定理都等于 $2s$。排好序就是： ``` @@ -90,5 +92,5 @@ - d[0] 到 d[3] 这 4 个相等。 - d[4]、d[5] 相等。 -- d[4] 等于 2 × d[0]。 +- d[4] 等于 $2 \times d[0]$。 排序的作用是：我们不知道哪一对是边、哪一对是对角线，但对角线的平方是边的 2 倍，一定比边长，排好序以后前 4 个就是边、后 2 个就是对角线，顺序问题就消失了。 @@ -103,5 +105,5 @@ ### 4. 为什么不用真实距离和 √2 -2026-04 那位发帖人说的是「对角线是边的 √2 倍」。如果照字面用真实距离写，代码是这样（`math.dist(a, b)` 是 Python 标准库里求两点距离的函数。`combinations(pts, 2)` 来自 `itertools`，依次给出 6 个点对）： +2026-04 那位发帖人说的是「对角线是边的 $\sqrt{2}$ 倍」。如果照字面用真实距离写，代码是这样（`math.dist(a, b)` 是 Python 标准库里求两点距离的函数。`combinations(pts, 2)` 来自 `itertools`，依次给出 6 个点对）： ```python @@ -117,19 +119,19 @@ ``` -问题出在浮点误差（floating-point error）：计算机里的浮点数用有限位二进制表示，√2 这样的无理数只能存一个近似值，乘一次、开一次根号都可能在最后一位上差一点。拿斜放 45° 的正方形 `[0,0] [1,1] [2,0] [1,-1]` 来说，边长是 √2，存成 `1.4142135623730951`。对角线是 2，存成精确的 `2.0`。而 `2 ** 0.5 * 1.4142135623730951` 算出来是 `2.0000000000000004`，和 `2.0` 不相等，函数返回 False，把一个正方形漏掉了。连边长 3、和坐标轴平行的正方形也会错：对角线 `math.dist((0,0), (3,3))` 算出来是 `4.242640687119285`，而 `2 ** 0.5 * 3` 是 `4.242640687119286`，最后一位差了 1。反过来，斜放但不是 45° 的正方形（比如边是从 (0,0) 到 (1,2) 这样的）在测试用例的穷举里碰巧全判对了。哪些输入会撞上舍入误差事先看不出来，这正是不该用浮点数比较的原因。 - -改成比距离的平方，这个比较就变成整数之间的 `10 == 2 * 5` 这种，没有误差。顺带一提，Python 的整数不会溢出。换成整数有固定位数的语言（比如 Java）时，按 LeetCode 的坐标范围，距离平方最大是 2 × (2 × 10⁴)² = 8 × 10⁸，再乘 2 也还在 32 位整数的上限 2.1 × 10⁹ 以内。 +问题出在浮点误差（floating-point error）：计算机里的浮点数用有限位二进制表示，$\sqrt{2}$ 这样的无理数只能存一个近似值，乘一次、开一次根号都可能在最后一位上差一点。拿斜放 45° 的正方形 `[0,0] [1,1] [2,0] [1,-1]` 来说，边长是 $\sqrt{2}$，存成 `1.4142135623730951`。对角线是 2，存成精确的 `2.0`。而 `2 ** 0.5 * 1.4142135623730951` 算出来是 `2.0000000000000004`，和 `2.0` 不相等，函数返回 False，把一个正方形漏掉了。连边长 3、和坐标轴平行的正方形也会错：对角线 `math.dist((0,0), (3,3))` 算出来是 `4.242640687119285`，而 `2 ** 0.5 * 3` 是 `4.242640687119286`，最后一位差了 1。反过来，斜放但不是 45° 的正方形（比如边是从 (0,0) 到 (1,2) 这样的）在测试用例的穷举里碰巧全判对了。哪些输入会撞上舍入误差事先看不出来，这正是不该用浮点数比较的原因。 + +改成比距离的平方，这个比较就变成整数之间的 `10 == 2 * 5` 这种，没有误差。顺带一提，Python 的整数不会溢出。换成整数有固定位数的语言（比如 Java）时，按 LeetCode 的坐标范围，距离平方最大是 $2 \times (2 \times 10^4)^2 = 8 \times 10^8$，再乘 2 也还在 32 位整数的上限 $2.1 \times 10^9$ 以内。 ### 5. 为什么这四条就够：分情况证明 -正方形一定满足这四条，第 3 节已经说了。反过来，设 6 个距离平方排好是 s, s, s, s, L, L，其中 s > 0，要证这 4 个点一定是正方形。顺带看清「对角线 = 2 × 边」这一条（代码里的 `diag == 2 * side`）到底挡住了什么。值为 L 的两对点下面叫「两条长线段」。两条不同的线段不可能两个端点都相同，所以它们只有两种关系：没有公共端点，或者恰好有一个公共端点。 +正方形一定满足这四条，第 3 节已经说了。反过来，设 6 个距离平方排好是 $s, s, s, s, L, L$，其中 $s > 0$，要证这 4 个点一定是正方形。顺带看清「$\text{对角线} = 2 \times \text{边}$」这一条（代码里的 `diag == 2 * side`）到底挡住了什么。值为 L 的两对点下面叫「两条长线段」。两条不同的线段不可能两个端点都相同，所以它们只有两种关系：没有公共端点，或者恰好有一个公共端点。 #### 情况一：两条长线段没有公共端点 -两条长线段把 4 个点分成两对，叫 AC 和 BD，剩下的 AB、BC、CD、DA 距离平方都是 s。平移和旋转不改变任何两点间的距离，所以可以把 A 放在原点、C 放在 x 轴正方向上：A = (0, 0)，C = (c, 0)，c = √L。设 B = (x, y)，B 到 A、C 的距离平方都是 s，即 x² + y² = (x − c)² + y²，展开消项得 x = c/2，也就是 B 在 AC 的垂直平分线上。代回 x² + y² = s 得 y² = s − c²/4。D 满足同样两个条件，所以也在 x = c/2 上，y 的平方也是 s − c²/4。B、D 的距离平方是 L ≥ s > 0，两点不重合，所以它们的 y 一正一负，BD² = 4y² = 4s − c² = 4s − L。条件要求 BD² = L，于是 4s − L = L，**L = 2s 在这种情况下自动成立**，y = ±c/2。记 t = c/2，四个点是 (0, 0)、(t, t)、(2t, 0)、(t, −t)。按这个顺序绕一圈，每一步的坐标差，也就是从一个角指向下一个角的向量（vector），依次是 (t, t)、(t, −t)、(−t, −t)、(−t, t)：长度平方都是 2t² = s。相邻两个向量的点积（dot product，对应分量相乘再相加）都是 0，点积为 0 就是互相垂直。四条边等长、四个角都是直角，是正方形。 +两条长线段把 4 个点分成两对，叫 AC 和 BD，剩下的 AB、BC、CD、DA 距离平方都是 s。平移和旋转不改变任何两点间的距离，所以可以把 A 放在原点、C 放在 x 轴正方向上：$A = (0, 0)$，$C = (c, 0)$，$c = \sqrt{L}$。设 $B = (x, y)$，B 到 A、C 的距离平方都是 s，即 $x^2 + y^2 = (x - c)^2 + y^2$，展开消项得 $x = c/2$，也就是 B 在 AC 的垂直平分线上。代回 $x^2 + y^2 = s$ 得 $y^2 = s - c^2/4$。D 满足同样两个条件，所以也在 $x = c/2$ 上，y 的平方也是 $s - c^2/4$。B、D 的距离平方是 $L \ge s > 0$，两点不重合，所以它们的 y 一正一负，$BD^2 = 4y^2 = 4s - c^2 = 4s - L$。条件要求 $BD^2 = L$，于是 $4s - L = L$，**$L = 2s$ 在这种情况下自动成立**，$y = \pm c/2$。记 $t = c/2$，四个点是 $(0, 0)$、$(t, t)$、$(2t, 0)$、$(t, -t)$。按这个顺序绕一圈，每一步的坐标差，也就是从一个角指向下一个角的向量（vector），依次是 $(t, t)$、$(t, -t)$、$(-t, -t)$、$(-t, t)$：长度平方都是 $2t^2 = s$。相邻两个向量的点积（dot product，对应分量相乘再相加）都是 0，点积为 0 就是互相垂直。四条边等长、四个角都是直角，是正方形。 #### 情况二：两条长线段有一个公共端点 -叫这个公共端点 P，两条长线段是 PQ、PR，第四个点叫 T。剩下的 PT、QR、QT、RT 距离平方都是 s。其中 QR、QT、RT 相等，说明 Q、R、T 是一个等边三角形（三条边一样长的三角形）。整体缩放不改变距离之间的比例，所以取 s = 1 来算。摆好坐标：Q = (−1/2, 0)，R = (1/2, 0)。T 到 Q、R 等距，按情况一的推导在 QR 的垂直平分线 x = 0 上，高是 √(1 − 1/4) = √3/2，取 T = (0, √3/2)（放在下方是镜像，结果一样）。PQ = PR，所以 P 也在 x = 0 上。PT² = 1，所以 P = (0, √3/2 + 1) 或 (0, √3/2 − 1)。算 PQ²： +叫这个公共端点 P，两条长线段是 PQ、PR，第四个点叫 T。剩下的 PT、QR、QT、RT 距离平方都是 s。其中 QR、QT、RT 相等，说明 Q、R、T 是一个等边三角形（三条边一样长的三角形）。整体缩放不改变距离之间的比例，所以取 $s = 1$ 来算。摆好坐标：$Q = (-1/2, 0)$，$R = (1/2, 0)$。T 到 Q、R 等距，按情况一的推导在 QR 的垂直平分线 $x = 0$ 上，高是 $\sqrt{1 - 1/4} = \sqrt{3}/2$，取 $T = (0, \sqrt{3}/2)$（放在下方是镜像，结果一样）。PQ = PR，所以 P 也在 $x = 0$ 上。$PT^2 = 1$，所以 $P = (0, \sqrt{3}/2 + 1)$ 或 $(0, \sqrt{3}/2 - 1)$。算 $PQ^2$： ``` @@ -137,15 +139,15 @@ ``` -取加号时，图形是一个等边三角形顶上再接一个点，像一只风筝（kite）。它的 6 个距离平方排好是 `[1, 1, 1, 1, 2+√3, 2+√3]`：最小 4 个相等、最大 2 个相等，**只有「2 倍」这一条能拦住它**，因为 2 + √3 不等于 2。取减号时排好是 `[2−√3, 2−√3, 1, 1, 1, 1]`，「最小 4 个相等」就不成立了。所以情况二永远过不了检查，只剩情况一，证毕。 - -整数坐标下风筝形根本画不出来，因为它需要一个三个顶点都在整数坐标上的等边三角形，而这不存在。理由是，顶点都是整数坐标的三角形，面积可以用鞋带公式（shoelace formula）算：面积 = |x₁(y₂ − y₃) + x₂(y₃ − y₁) + x₃(y₁ − y₂)| / 2，分子是整数，所以面积是有理数。而等边三角形的面积是 (√3/4) × 边长²，边长² 是正整数，面积是无理数，两者矛盾。所以整数坐标下去掉「2 倍」这一条也不会判错：情况一里它自动成立，情况二不会出现。尽管如此，代码里还是留着它：它不花任何代价，坐标换成浮点数时也照样对。 - -最后是「边长大于 0」这一条（代码里的 `side > 0`）。它要挡的只有一种输入：4 个点完全重合。这时 6 个距离全是 0，「0 == 0」「0 == 2 × 0」都成立，去掉这一条会返回 True。其他有重合点的情况，别的条件已经能挡住：重合的点对距离是 0，而要让最小的 4 个都是 0，至少要有 4 对点重合。3 个点重合只产生 3 对，两组各 2 个点重合只产生 2 对，都不够 4 对。只有 4 个点全部重合才有 6 对。所以只要不是全部重合，d[0] 和 d[3] 就不会都是 0，比如两对重合点 `[0,0] [0,0] [1,1] [1,1]` 排好是 `[0, 0, 2, 2, 2, 2]`，d[0] ≠ d[3]。 +取加号时，图形是一个等边三角形顶上再接一个点，像一只风筝（kite）。它的 6 个距离平方排好是 `[1, 1, 1, 1, 2+√3, 2+√3]`：最小 4 个相等、最大 2 个相等，**只有「2 倍」这一条能拦住它**，因为 $2 + \sqrt{3}$ 不等于 2。取减号时排好是 `[2−√3, 2−√3, 1, 1, 1, 1]`，「最小 4 个相等」就不成立了。所以情况二永远过不了检查，只剩情况一，证毕。 + +整数坐标下风筝形根本画不出来，因为它需要一个三个顶点都在整数坐标上的等边三角形，而这不存在。理由是，顶点都是整数坐标的三角形，面积可以用鞋带公式（shoelace formula）算：$\text{面积} = |x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)| / 2$，分子是整数，所以面积是有理数。而等边三角形的面积是 $(\sqrt{3}/4) \times \text{边长}^2$，$\text{边长}^2$ 是正整数，面积是无理数，两者矛盾。所以整数坐标下去掉「2 倍」这一条也不会判错：情况一里它自动成立，情况二不会出现。尽管如此，代码里还是留着它：它不花任何代价，坐标换成浮点数时也照样对。 + +最后是「边长大于 0」这一条（代码里的 `side > 0`）。它要挡的只有一种输入：4 个点完全重合。这时 6 个距离全是 0，「0 == 0」「0 == 2 × 0」都成立，去掉这一条会返回 True。其他有重合点的情况，别的条件已经能挡住：重合的点对距离是 0，而要让最小的 4 个都是 0，至少要有 4 对点重合。3 个点重合只产生 3 对，两组各 2 个点重合只产生 2 对，都不够 4 对。只有 4 个点全部重合才有 6 对。所以只要不是全部重合，d[0] 和 d[3] 就不会都是 0，比如两对重合点 `[0,0] [0,0] [1,1] [1,1]` 排好是 `[0, 0, 2, 2, 2, 2]`，$d[0] \ne d[3]$。 ### 6. 第二种判法：已知一条对角线，推出另外两个角 -这个做法在 4 个点的题里不比第 3 节的排序做法省事，但面经里数正方形的 O(n²) 做法靠的就是它，所以在这里先见一面。拿它数 n 个点里的正方形、去重、处理重复点，都在 [[q:everpure-count-squares]]。这里只讲 4 个点怎么用，以及为什么对。 - -第 3 节说过任何正方形都满足那四条，而正方形的两条对角线没有公共端点，属于第 5 节的情况一，所以按情况一的推导，任何正方形摆好坐标后都是 (0, 0)、(t, t)、(2t, 0)、(t, −t)。从这组坐标能直接读出对角线的性质：AC 从 (0, 0) 到 (2t, 0)，BD 从 (t, t) 到 (t, −t)，长度都是 2t，中点都是 (t, 0)，一条横、一条竖，互相垂直。所以只要知道一条对角线 AC，另一条对角线 BD 就完全确定了：中点和 AC 相同，方向是 AC 转 90°，长度和 AC 一样。记 (dx, dy) = (C.x − A.x, C.y − A.y)，也就是从 A 指向 C 的向量。一个向量转 90° 就是把两个分量对调、再给其中一个变号，(dx, dy) 转完是 (−dy, dx)（可以拿 (1, 0) 验证：它转完是 (0, 1)，从向右变成向上）。于是： +这个做法在 4 个点的题里不比第 3 节的排序做法省事，但面经里数正方形的 $O(n^2)$ 做法靠的就是它，所以在这里先见一面。拿它数 n 个点里的正方形、去重、处理重复点，都在 [[q:everpure-count-squares]]。这里只讲 4 个点怎么用，以及为什么对。 + +第 3 节说过任何正方形都满足那四条，而正方形的两条对角线没有公共端点，属于第 5 节的情况一，所以按情况一的推导，任何正方形摆好坐标后都是 $(0, 0)$、$(t, t)$、$(2t, 0)$、$(t, -t)$。从这组坐标能直接读出对角线的性质：AC 从 $(0, 0)$ 到 $(2t, 0)$，BD 从 $(t, t)$ 到 $(t, -t)$，长度都是 $2t$，中点都是 $(t, 0)$，一条横、一条竖，互相垂直。所以只要知道一条对角线 AC，另一条对角线 BD 就完全确定了：中点和 AC 相同，方向是 AC 转 90°，长度和 AC 一样。记 $(dx, dy) = (C.x - A.x, C.y - A.y)$，也就是从 A 指向 C 的向量。一个向量转 90° 就是把两个分量对调、再给其中一个变号，$(dx, dy)$ 转完是 $(-dy, dx)$（可以拿 (1, 0) 验证：它转完是 (0, 1)，从向右变成向上）。于是： ``` @@ -154,11 +156,11 @@ ``` -拿斜放的例子验算：A = (0, 0)，C = (1, 3)，dx = 1、dy = 3，得 B = ((0 + 1 − 3)/2, (0 + 3 + 1)/2) = (−1, 2)，D = ((0 + 1 + 3)/2, (0 + 3 − 1)/2) = (2, 1)，正好是另外两个输入点。 - -除以 2 可能得到半整数，比如 A = (0, 0)、C = (1, 0) 时 B = (0.5, 0.5)。最省事的办法是**把所有坐标都乘 2 再比较**：直接算 2B = (A.x + C.x − dy, A.y + C.y + dx)，全是整数，再拿它和「另外两个输入点的坐标乘 2」比。乘 2 不改变谁和谁相等，又避开了浮点数。不能用整除 `// 2` 代替：整除会把半整数向下取整，取整后的点可能恰好撞上一个真实的输入点。比如输入 `[0,1] [0,2] [1,0] [2,2]`，拿 (0,1)、(2,2) 当对角线，真正的 B、D 是 (0.5, 2.5) 和 (1.5, 0.5)，整除后变成 (0, 2) 和 (1, 0)，正好是另外两个输入点，于是一个不是正方形的输入被判成 True。 +拿斜放的例子验算：$A = (0, 0)$，$C = (1, 3)$，$dx = 1$、$dy = 3$，得 $B = ((0 + 1 - 3)/2, (0 + 3 + 1)/2) = (-1, 2)$，$D = ((0 + 1 + 3)/2, (0 + 3 - 1)/2) = (2, 1)$，正好是另外两个输入点。 + +除以 2 可能得到半整数，比如 $A = (0, 0)$、$C = (1, 0)$ 时 $B = (0.5, 0.5)$。最省事的办法是**把所有坐标都乘 2 再比较**：直接算 $2B = (A.x + C.x - dy, A.y + C.y + dx)$，全是整数，再拿它和「另外两个输入点的坐标乘 2」比。乘 2 不改变谁和谁相等，又避开了浮点数。不能用整除 `// 2` 代替：整除会把半整数向下取整，取整后的点可能恰好撞上一个真实的输入点。比如输入 `[0,1] [0,2] [1,0] [2,2]`，拿 (0,1)、(2,2) 当对角线，真正的 B、D 是 (0.5, 2.5) 和 (1.5, 0.5)，整除后变成 (0, 2) 和 (1, 0)，正好是另外两个输入点，于是一个不是正方形的输入被判成 True。 4 个点的判断就是：p1 的对角一定是 p2、p3、p4 之一，三种都试一遍，有一种算出来的两个角正好是剩下两个点，就是正方形。假设的对角和 p1 重合时（dx、dy 都是 0），算出的两个角也都等于 p1，「4 个点全部重合」会被判成 True，所以这种情况要跳过。 -这个做法是对的，要分两半看。先看「试成功就是正方形」。设 M 是 AC 的中点，h 是从 M 指向 C 的向量（半条对角线），所以 A = M − h、C = M + h。r 是 h 转 90° 得到的向量，上面的公式就是 B = M + r、D = M − r。|h| 记 h 的长度。B − A = h + r，所以 AB 的距离平方是 |h + r|² = |h|² + |r|² + 2 h·r（长度平方就是向量和自己的点积，(h + r)·(h + r) 展开即得）。h 和 r 垂直，h·r = 0，又 |r| = |h|，于是 AB² = 2|h|²。BC、CD、DA 对应的向量是 h − r、−h − r、r − h，同样算都是 2|h|²。AC² = |2h|² = 4|h|²，BD² = |2r|² = 4|h|²。6 个值排好正是 s, s, s, s, 2s, 2s，s = 2|h|² > 0，按第 5 节，A、B、C、D 是正方形。再看「是正方形就一定试得成功」：p1 恰好有一个对角顶点，试到它的那一次，另一条对角线的中点、方向、长度都和上一段读出的性质一致，算出来的 B、D 正是另外两个顶点，这次尝试成功。 +这个做法是对的，要分两半看。先看「试成功就是正方形」。设 M 是 AC 的中点，h 是从 M 指向 C 的向量（半条对角线），所以 $A = M - h$、$C = M + h$。r 是 h 转 90° 得到的向量，上面的公式就是 $B = M + r$、$D = M - r$。$|h|$ 记 h 的长度。$B - A = h + r$，所以 AB 的距离平方是 $|h + r|^2 = |h|^2 + |r|^2 + 2\, h \cdot r$（长度平方就是向量和自己的点积，$(h + r) \cdot (h + r)$ 展开即得）。h 和 r 垂直，$h \cdot r = 0$，又 $|r| = |h|$，于是 $AB^2 = 2|h|^2$。BC、CD、DA 对应的向量是 $h - r$、$-h - r$、$r - h$，同样算都是 $2|h|^2$。$AC^2 = |2h|^2 = 4|h|^2$，$BD^2 = |2r|^2 = 4|h|^2$。6 个值排好正是 $s, s, s, s, 2s, 2s$，$s = 2|h|^2 > 0$，按第 5 节，A、B、C、D 是正方形。再看「是正方形就一定试得成功」：p1 恰好有一个对角顶点，试到它的那一次，另一条对角线的中点、方向、长度都和上一段读出的性质一致，算出来的 B、D 正是另外两个顶点，这次尝试成功。 ```python @@ -205,11 +207,11 @@ ## 复杂度 -- 时间 O(1)：输入固定是 4 个点，只算 6 个距离、排序 6 个数。第 6 节的对角线做法也是 O(1)，最多试 3 次。 -- 空间 O(1)：只存 6 个数。 +- 时间 $O(1)$：输入固定是 4 个点，只算 6 个距离、排序 6 个数。第 6 节的对角线做法也是 $O(1)$，最多试 3 次。 +- 空间 $O(1)$：只存 6 个数。 ## 易错点 - **把输入顺序当成绕一圈的顺序**（思路第 2 节）：点给乱了会漏掉正方形，有重合点会误判。 -- **用真实距离比 √2 倍**（第 4 节）：浮点误差让 45° 斜放的正方形判成 False。比距离的平方就全是整数。 +- **用真实距离比 $\sqrt{2}$ 倍**（第 4 节）：浮点误差让 45° 斜放的正方形判成 False。比距离的平方就全是整数。 - **漏了「边长大于 0」**（第 5 节）：4 个点完全重合时其他三条都成立，会返回 True。 - **漏了「对角线 = 2 倍边」**（第 5 节）：整数坐标下不会出错，浮点坐标下等边三角形加一个点的风筝形会被判成正方形。 @@ -225,5 +227,5 @@ **错的版本和对的版本放在同一组输入上**： -| 输入 | 按输入顺序（第 2 节） | 真实距离 + √2（第 4 节） | 主解法 | 对角线做法 | +| 输入 | 按输入顺序（第 2 节） | 真实距离 + $\sqrt{2}$（第 4 节） | 主解法 | 对角线做法 | | --- | --- | --- | --- | --- | | `[0,0] [1,1] [1,0] [0,1]`（交叉顺序的正方形） | **False** | True | True | True | @@ -236,5 +238,5 @@ 主解法去掉「边长大于 0」以后，4 个点重合返回 **True**。`[0,0] [0,0] [0,0] [1,1]`（距离平方 `[0, 0, 0, 2, 2, 2]`）和 `[0,0] [0,0] [1,1] [1,1]`（`[0, 0, 2, 2, 2, 2]`）仍然返回 False，和第 5 节的分析一致。 -**风筝形**（第 5 节）：点取 (−0.5, 0)、(0.5, 0)、(0, √3/2)、(0, √3/2 + 1)，6 个距离平方算出来是 `[1, 1, 1, 1, 3.732051, 3.732051]`，3.732051 正是 2 + √3。Follow-up 第 2 条的浮点版返回 False。把它的「2 倍」那一条去掉，返回 **True**。第四个点换成 (0, √3/2 − 1)，距离平方是 `[0.267949, 0.267949, 1, 1, 1, 1]`，两个版本都返回 False。 +**风筝形**（第 5 节）：点取 $(-0.5, 0)$、$(0.5, 0)$、$(0, \sqrt{3}/2)$、$(0, \sqrt{3}/2 + 1)$，6 个距离平方算出来是 `[1, 1, 1, 1, 3.732051, 3.732051]`，3.732051 正是 $2 + \sqrt{3}$。Follow-up 第 2 条的浮点版返回 False。把它的「2 倍」那一条去掉，返回 **True**。第四个点换成 $(0, \sqrt{3}/2 - 1)$，距离平方是 `[0.267949, 0.267949, 1, 1, 1, 1]`，两个版本都返回 False。 **穷举**：在 x、y 都取 0 到 4 的 25 个格点上任取 4 个点（允许重复），共 20475 组，其中正方形 50 个（30 个和坐标轴平行，20 个斜放）。 @@ -246,31 +248,31 @@ | 浮点版 `valid_square_float`（Follow-up 第 2 条） | 0 | 0 | 0 | | 主解法去掉「2 倍」那一条 | 0 | 0 | 0 | -| 真实距离 + √2 | 14 | 0 | 14 | +| 真实距离 + $\sqrt{2}$ | 14 | 0 | 14 | | 对角线做法用 `// 2` 取整 | 20 | 20 | 0 | | 按输入顺序（每组的所有排列都试，共 390625 个输入） | 1425 | 625 | 800 | | 按输入顺序 + 边长大于 0（同上，所有排列） | 1400 | 600 | 800 | -真实距离 + √2 漏掉的 14 个是：45° 斜放的 10 个（全部），以及边长 3、和坐标轴平行的 4 个。斜放但不是 45° 的 10 个全判对。 - -**第 6 节的距离模式**：随机取 5000 条对角线 AC（整数坐标，A ≠ C），按公式算出 B、D，这四个点的 6 个距离平方全部是 s, s, s, s, 2s, 2s，5000/5000。 - -**大坐标随机测试**：随机生成 20000 组，坐标绝对值不超过 10⁴，一半是随机斜放的正方形，一半是把正方形的一个角挪 1 格（实际得到 9990 个正方形）。主解法和对角线做法都和标准答案一致，0 次不同。 - -**浮点坐标**（Follow-up 第 2 条）：每一档 2000 个真正的正方形，表里是判成 True 的个数。「绝对容差」是固定的 10⁻⁹，「只按 d[5]」是 10⁻⁹ × d[5]（漏掉第 2 项误差）。 +真实距离 + $\sqrt{2}$ 漏掉的 14 个是：45° 斜放的 10 个（全部），以及边长 3、和坐标轴平行的 4 个。斜放但不是 45° 的 10 个全判对。 + +**第 6 节的距离模式**：随机取 5000 条对角线 AC（整数坐标，$A \ne C$），按公式算出 B、D，这四个点的 6 个距离平方全部是 $s, s, s, s, 2s, 2s$，5000/5000。 + +**大坐标随机测试**：随机生成 20000 组，坐标绝对值不超过 $10^4$，一半是随机斜放的正方形，一半是把正方形的一个角挪 1 格（实际得到 9990 个正方形）。主解法和对角线做法都和标准答案一致，0 次不同。 + +**浮点坐标**（Follow-up 第 2 条）：每一档 2000 个真正的正方形，表里是判成 True 的个数。「绝对容差」是固定的 $10^{-9}$，「只按 d[5]」是 $10^{-9} \times d[5]$（漏掉第 2 项误差）。 | 场景 | `==` | 绝对容差 | 只按 d[5] | 本节的写法 | | --- | --- | --- | --- | --- | -| 中心在 ±1 以内、大小 0.1 到 1 | 73 | 2000 | 2000 | 2000 | -| 中心在 ±10³、大小 10² 到 10³ | 50 | 1540 | 2000 | 2000 | -| 中心在 ±10⁶、大小 10⁵ 到 10⁶ | 65 | 65 | 2000 | 2000 | -| 坐标在 ±10⁴、边长 10⁻³ | 577 | 2000 | 1647 | 2000 | -| 坐标在 ±10⁶、边长 10⁻³ | 820 | 2000 | 822 | 2000 | -| 坐标在 ±10⁸、边长 1 | 645 | 721 | 737 | 2000 | - -最后一行的一个具体例子：边长 1、一个角在 (10⁸, 0) 附近，4 条边的距离平方算出来是 `1.0000000004873861`（两条）和 `1.0000000049544568`（两条），最大和最小差 4.5 × 10⁻⁹。10⁻⁹ × d[5] 只有 2 × 10⁻⁹，判 False。本节的 tol ≈ 1.4 × 10⁻⁵，判 True。边长 10⁻⁶ 的正方形，绝对容差判 False（当成重合点），另外两种判 True。另取 36000 个随机正方形（坐标 ±1 到 ±10⁸，边长 10⁻³ 到 10³），本该相等的两个距离平方之差最大是 (d[5] + M × √d[5]) × 2⁻⁵³ 的 3.95 倍，在 Follow-up 第 2 条推算的十几倍以内。 - -不是正方形的输入：单位正方形把一个角挪 10⁻³、10⁻⁵、10⁻⁷，放在原点或坐标 10⁶ 处，三种容差都判 False。容差会放过更小的偏差：放在坐标 10⁶ 处时 tol ≈ 1.4 × 10⁻⁷，一个角挪 5 × 10⁻⁸ 本节的写法判 True，挪 10⁻⁷ 判 False。 - -**只许平行于坐标轴**（Follow-up 第 3 条）：`[0,0] [0,2] [2,0] [2,2]` → True，斜放的正方形 `[0,0] [1,1] [2,0] [1,-1]` → False，2 × 3 的长方形 `[0,0] [0,2] [3,0] [3,2]` → False，4 点重合 → False，三个角加一个重复的角 `[0,0] [0,2] [2,2] [2,2]` → False。格点穷举判错 0 个。 +| 中心在 $\pm 1$ 以内、大小 0.1 到 1 | 73 | 2000 | 2000 | 2000 | +| 中心在 $\pm 10^3$、大小 $10^2$ 到 $10^3$ | 50 | 1540 | 2000 | 2000 | +| 中心在 $\pm 10^6$、大小 $10^5$ 到 $10^6$ | 65 | 65 | 2000 | 2000 | +| 坐标在 $\pm 10^4$、边长 $10^{-3}$ | 577 | 2000 | 1647 | 2000 | +| 坐标在 $\pm 10^6$、边长 $10^{-3}$ | 820 | 2000 | 822 | 2000 | +| 坐标在 $\pm 10^8$、边长 1 | 645 | 721 | 737 | 2000 | + +最后一行的一个具体例子：边长 1、一个角在 $(10^8, 0)$ 附近，4 条边的距离平方算出来是 `1.0000000004873861`（两条）和 `1.0000000049544568`（两条），最大和最小差 $4.5 \times 10^{-9}$。$10^{-9} \times d[5]$ 只有 $2 \times 10^{-9}$，判 False。本节的 $\mathrm{tol} \approx 1.4 \times 10^{-5}$，判 True。边长 $10^{-6}$ 的正方形，绝对容差判 False（当成重合点），另外两种判 True。另取 36000 个随机正方形（坐标 $\pm 1$ 到 $\pm 10^8$，边长 $10^{-3}$ 到 $10^3$），本该相等的两个距离平方之差最大是 $(d[5] + M \times \sqrt{d[5]}) \times 2^{-53}$ 的 3.95 倍，在 Follow-up 第 2 条推算的十几倍以内。 + +不是正方形的输入：单位正方形把一个角挪 $10^{-3}$、$10^{-5}$、$10^{-7}$，放在原点或坐标 $10^6$ 处，三种容差都判 False。容差会放过更小的偏差：放在坐标 $10^6$ 处时 $\mathrm{tol} \approx 1.4 \times 10^{-7}$，一个角挪 $5 \times 10^{-8}$ 本节的写法判 True，挪 $10^{-7}$ 判 False。 + +**只许平行于坐标轴**（Follow-up 第 3 条）：`[0,0] [0,2] [2,0] [2,2]` → True，斜放的正方形 `[0,0] [1,1] [2,0] [1,-1]` → False，$2 \times 3$ 的长方形 `[0,0] [0,2] [3,0] [3,2]` → False，4 点重合 → False，三个角加一个重复的角 `[0,0] [0,2] [2,2] [2,2]` → False。格点穷举判错 0 个。 ## Follow-up @@ -278,5 +280,5 @@ ### 1. 一堆点里能组成多少个正方形 -记了 follow-up 的几篇面经都接这一问：给 n 个点，数它们能组成多少个正方形，并要求优化，有的面试官明确要求从 O(n⁴) 到 O(n³) 再到 O(n²)。2017 年和 2026 年各有一位发帖人说这一问讲清思路就行，不用写代码。O(n⁴) 就是把本页的 `valid_square` 套在每一组 4 个点上。O(n²) 用的是思路第 6 节：把所有点放进哈希集合，枚举每一对点当对角线，O(1) 算出另外两个角并查集合。每个正方形有两条对角线，会被数两次，最后除以 2。三级的完整推导、O(n³) 那一步怎么填、输入有重复点怎么办，都在 [[q:everpure-count-squares]]，这里不重复。 +记了 follow-up 的几篇面经都接这一问：给 n 个点，数它们能组成多少个正方形，并要求优化，有的面试官明确要求从 $O(n^4)$ 到 $O(n^3)$ 再到 $O(n^2)$。2017 年和 2026 年各有一位发帖人说这一问讲清思路就行，不用写代码。$O(n^4)$ 就是把本页的 `valid_square` 套在每一组 4 个点上。$O(n^2)$ 用的是思路第 6 节：把所有点放进哈希集合，枚举每一对点当对角线，$O(1)$ 算出另外两个角并查集合。每个正方形有两条对角线，会被数两次，最后除以 2。三级的完整推导、$O(n^3)$ 那一步怎么填、输入有重复点怎么办，都在 [[q:everpure-count-squares]]，这里不重复。 ### 2. 坐标是浮点数 @@ -284,10 +286,10 @@ 面经里没有人被问到这一条，下面是按常见的浮点处理方式准备的。浮点坐标下，同一个正方形算出来的 6 个距离平方会在最后几位上有差别，用 `==` 比较大多会判错（测试用例里的浮点表）。要改成「差得足够小就算相等」，这个「足够小」叫容差（tolerance）。容差取多大，要从误差的来源倒推。 -双精度浮点数（double）有 53 位二进制有效数字，一次运算的相对舍入误差最多 2⁻⁵³ ≈ 1.1 × 10⁻¹⁶。一次判断里的误差有两个来源： +双精度浮点数（double）有 53 位二进制有效数字，一次运算的相对舍入误差最多 $2^{-53} \approx 1.1 \times 10^{-16}$。一次判断里的误差有两个来源： 1. **算距离平方本身的舍入**。减法、平方、相加各带一次相对误差，结果的误差和距离平方 d 本身成比例：d 越大，误差的绝对值越大。所以容差不能是一个固定的绝对值，要有一项正比于 d，下面用最长的 d[5]。 -2. **坐标本身的舍入**。坐标 x 存成浮点数时就已经带着 |x| × 10⁻¹⁶ 量级的误差，坐标越大误差越大，和正方形多大无关。坐标差 dx 带着这个误差 δ，平方以后误差变成 2 × |dx| × δ 量级，也就是 √d × M × 10⁻¹⁶，M 是坐标的最大绝对值。正方形很小、却放在离原点很远的地方时，这一项远大于第 1 项。 - -把两项加起来，再乘一个安全系数 eps，就是容差：tol = eps × (d[5] + M × √d[5])。eps 取 10⁻¹³，约是单次舍入误差 2⁻⁵³ 的 900 倍。每个距离平方只经过两次减法、两次平方、一次加法，按上面两项估算，两个距离平方之差的误差不超过 (d[5] + M × √d[5]) 乘单次舍入误差的十几倍【推断】（测试用例里有实测）。900 倍是在这之上再留出很大的余量。 +2. **坐标本身的舍入**。坐标 x 存成浮点数时就已经带着 $|x| \times 10^{-16}$ 量级的误差，坐标越大误差越大，和正方形多大无关。坐标差 dx 带着这个误差 δ，平方以后误差变成 $2 \times |dx| \times \delta$ 量级，也就是 $\sqrt{d} \times M \times 10^{-16}$，M 是坐标的最大绝对值。正方形很小、却放在离原点很远的地方时，这一项远大于第 1 项。 + +把两项加起来，再乘一个安全系数 eps，就是容差：$\mathrm{tol} = \mathrm{eps} \times (d[5] + M \times \sqrt{d[5]})$。eps 取 $10^{-13}$，约是单次舍入误差 $2^{-53}$ 的 900 倍。每个距离平方只经过两次减法、两次平方、一次加法，按上面两项估算，两个距离平方之差的误差不超过 $(d[5] + M \times \sqrt{d[5]})$ 乘单次舍入误差的十几倍【推断】（测试用例里有实测）。900 倍是在这之上再留出很大的余量。 ```python @@ -310,11 +312,11 @@ `d[0] > tol` 是「边长大于 0」的浮点版：边长平方要明显大于误差，否则视作重合。「2 倍」那一条必须保留：浮点坐标可以画出第 5 节的风筝形。 -不能照常见的习惯随手取 eps = 10⁻⁹：坐标在 10⁶ 附近、边长 10⁻³ 时，M × √d[5] ≈ 10⁶ × 1.4 × 10⁻³ = 1.4 × 10³，乘 10⁻⁹ 得 1.4 × 10⁻⁶，比边长平方 10⁻⁶ 本身还大，真正的正方形会被 `d[0] > tol` 当成重合点拒掉。安全系数要和误差的真实量级（10⁻¹⁶）挂钩，不能凭感觉。测试用例里把这种写法和两种常见写法放在同一批随机正方形上比：固定的绝对容差在大图形上失效，对应第 1 项误差。只按 d[5] 换算的容差在「小正方形放得很远」时失效，对应第 2 项误差。本节的写法都判对。 - -代价是比容差小的真实偏差会被当成相等。把一个角沿边的方向挪 e，那条边的距离平方从 a² 变成 (a + e)²，大约多出 2 × a × e（a 是边长），这个变化要超过 tol 才看得出来，所以小于 tol / (2a) 量级的偏差会被放过（测试用例里有坐标 10⁶ 处的实测）。这是浮点判断躲不开的代价。坐标是整数时仍然用主解法。这里的 eps 针对的是「坐标只经过了存储和这几步运算」的情况，如果坐标是测量来的、或者是别的计算算出来的，误差比舍入误差大得多，容差就要按数据的实际精度定，这一点要和面试官确认。 +不能照常见的习惯随手取 $\mathrm{eps} = 10^{-9}$：坐标在 $10^6$ 附近、边长 $10^{-3}$ 时，$M \times \sqrt{d[5]} \approx 10^6 \times 1.4 \times 10^{-3} = 1.4 \times 10^3$，乘 $10^{-9}$ 得 $1.4 \times 10^{-6}$，比边长平方 $10^{-6}$ 本身还大，真正的正方形会被 `d[0] > tol` 当成重合点拒掉。安全系数要和误差的真实量级（$10^{-16}$）挂钩，不能凭感觉。测试用例里把这种写法和两种常见写法放在同一批随机正方形上比：固定的绝对容差在大图形上失效，对应第 1 项误差。只按 d[5] 换算的容差在「小正方形放得很远」时失效，对应第 2 项误差。本节的写法都判对。 + +代价是比容差小的真实偏差会被当成相等。把一个角沿边的方向挪 e，那条边的距离平方从 $a^2$ 变成 $(a + e)^2$，大约多出 $2 \times a \times e$（a 是边长），这个变化要超过 tol 才看得出来，所以小于 $\mathrm{tol} / (2a)$ 量级的偏差会被放过（测试用例里有坐标 $10^6$ 处的实测）。这是浮点判断躲不开的代价。坐标是整数时仍然用主解法。这里的 eps 针对的是「坐标只经过了存储和这几步运算」的情况，如果坐标是测量来的、或者是别的计算算出来的，误差比舍入误差大得多，容差就要按数据的实际精度定，这一点要和面试官确认。 ### 3. 只算边和坐标轴平行的正方形 -如果面试官说正方形的边一定和 x 轴、y 轴平行，判断就不需要距离了。这样的正方形四个角一定是 (x₀, y₀)、(x₀ + k, y₀)、(x₀, y₀ + k)、(x₀ + k, y₀ + k)，k > 0。所以条件是：4 个点里恰好有 2 种不同的 x、2 种不同的 y。两种 x 的差等于两种 y 的差。4 个输入点正好是这两种 x 和两种 y 组合出的 4 个角。 +如果面试官说正方形的边一定和 x 轴、y 轴平行，判断就不需要距离了。这样的正方形四个角一定是 $(x_0, y_0)$、$(x_0 + k, y_0)$、$(x_0, y_0 + k)$、$(x_0 + k, y_0 + k)$，$k > 0$。所以条件是：4 个点里恰好有 2 种不同的 x、2 种不同的 y。两种 x 的差等于两种 y 的差。4 个输入点正好是这两种 x 和两种 y 组合出的 4 个角。 ```python @@ -329,5 +331,5 @@ ``` -最后一行就够，因为 `corners` 有 4 个不同的角，4 个输入点组成的集合等于它，说明 4 个输入点互不相同、而且正好覆盖 4 个角。三个角加一个重复的角，集合里只有 3 个点，不等于 `corners`，返回 False。有两种不同的 x，k = xs[1] − xs[0] 自然大于 0，重合点的情况也就排除了。斜放的正方形至少有 3 种不同的 x，第一个 `if` 就返回 False。 +最后一行就够，因为 `corners` 有 4 个不同的角，4 个输入点组成的集合等于它，说明 4 个输入点互不相同、而且正好覆盖 4 个角。三个角加一个重复的角，集合里只有 3 个点，不等于 `corners`，返回 False。有两种不同的 x，$k = xs[1] - xs[0]$ 自然大于 0，重合点的情况也就排除了。斜放的正方形至少有 3 种不同的 x，第一个 `if` 就返回 False。 ## 英文讲法
meta
@@ -1,5 +1,5 @@ { "depth_guide": "2026-10-23", - "rewritten_by": "local", - "rewritten_at": "2026-10-25" + "rewritten_by": "cloud:20261026-2311", + "rewritten_at": "2026-10-27" }