更新题目 593. Valid Square
题目 lc593 · 修改（rev 8） · · 2026-10-27 12:09
body
@@ -39,4 +39,6 @@ | 输入是什么形式？用什么语言？ | 面经没给签名，也没说语言。按 LeetCode 的 4 个参数写 | 如果给的是一个装 4 个点的列表 `points`，调用 `valid_square(*points)` 即可。用 Java 要注意距离平方会不会超出 `int`，见思路第 4 节末尾 | +> [!say] Before I start: can the square be rotated, or are its sides always parallel to the axes? Are the coordinates integers? And should four identical points count as a square? I'll assume rotation is allowed, integer coordinates, and that a square needs a positive side length. + ## 面经里怎么考的 @@ -95,4 +97,6 @@ 排序的作用是：我们不知道哪一对是边、哪一对是对角线，但对角线的平方是边的 2 倍，一定比边长，排好序以后前 4 个就是边、后 2 个就是对角线，顺序问题就消失了。 + +> [!say] I don't rely on the input order. I compute all six pairwise squared distances and sort them. For a square, the four smallest are the sides and must be equal and non-zero, the two largest are the diagonals and must be equal, and the diagonal must be exactly twice the side. 拿题目里的两个例子走一遍： @@ -123,4 +127,6 @@ 改成比距离的平方，这个比较就变成整数之间的 `10 == 2 * 5` 这种，没有误差。顺带一提，Python 的整数不会溢出。换成整数有固定位数的语言（比如 Java）时，按 LeetCode 的坐标范围，距离平方最大是 $2 \times (2 \times 10^4)^2 = 8 \times 10^8$，再乘 2 也还在 32 位整数的上限 $2.1 \times 10^9$ 以内。 +> [!say] I use squared distances so everything stays in integers. If I compared real distances against the square root of two, a square rotated by forty-five degrees could fail because of floating-point rounding. + ### 5. 为什么这四条就够：分情况证明 @@ -144,4 +150,6 @@ 最后是「边长大于 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]$。 + +> [!say] This is sufficient, by case analysis. If the two long segments don't share an endpoint, they are the diagonals. The other two points must lie on the perpendicular bisector of one diagonal, at side distance from both of its ends, and the only way the second diagonal can have the same length is the square. If the long segments do share an endpoint, three of the points form an equilateral triangle, and the ratio of the long squared distance to the short one is two plus or minus root three, never two, so the ratio check rejects it. ### 6. 第二种判法：已知一条对角线，推出另外两个角 @@ -182,4 +190,6 @@ ``` +> [!say] For the follow-up I'll use a different building block: given one diagonal, the other two corners are fixed: the midpoint plus or minus the diagonal vector rotated by ninety degrees, halved. Doubling all coordinates keeps it in integers. + ## 代码 @@ -316,4 +326,6 @@ 代价是比容差小的真实偏差会被当成相等。把一个角沿边的方向挪 e，那条边的距离平方从 $a^2$ 变成 $(a + e)^2$，大约多出 $2 \times a \times e$（a 是边长），这个变化要超过 tol 才看得出来，所以小于 $\mathrm{tol} / (2a)$ 量级的偏差会被放过（测试用例里有坐标 $10^6$ 处的实测）。这是浮点判断躲不开的代价。坐标是整数时仍然用主解法。这里的 eps 针对的是「坐标只经过了存储和这几步运算」的情况，如果坐标是测量来的、或者是别的计算算出来的，误差比舍入误差大得多，容差就要按数据的实际精度定，这一点要和面试官确认。 +> [!say] With floating-point coordinates I'd compare within a tolerance that scales with both the size of the figure and the magnitude of the coordinates, because the coordinates themselves carry rounding error proportional to their size. + ### 3. 只算边和坐标轴平行的正方形 @@ -332,16 +344,2 @@ 最后一行就够，因为 `corners` 有 4 个不同的角，4 个输入点组成的集合等于它，说明 4 个输入点互不相同、而且正好覆盖 4 个角。三个角加一个重复的角，集合里只有 3 个点，不等于 `corners`，返回 False。有两种不同的 x，$k = xs[1] - xs[0]$ 自然大于 0，重合点的情况也就排除了。斜放的正方形至少有 3 种不同的 x，第一个 `if` 就返回 False。 - -## 英文讲法 - -> [!say] Before I start: can the square be rotated, or are its sides always parallel to the axes? Are the coordinates integers? And should four identical points count as a square? I'll assume rotation is allowed, integer coordinates, and that a square needs a positive side length. - -> [!say] I don't rely on the input order. I compute all six pairwise squared distances and sort them. For a square, the four smallest are the sides and must be equal and non-zero, the two largest are the diagonals and must be equal, and the diagonal must be exactly twice the side. - -> [!say] I use squared distances so everything stays in integers. If I compared real distances against the square root of two, a square rotated by forty-five degrees could fail because of floating-point rounding. - -> [!say] This is sufficient, by case analysis. If the two long segments don't share an endpoint, they are the diagonals. The other two points must lie on the perpendicular bisector of one diagonal, at side distance from both of its ends, and the only way the second diagonal can have the same length is the square. If the long segments do share an endpoint, three of the points form an equilateral triangle, and the ratio of the long squared distance to the short one is two plus or minus root three, never two, so the ratio check rejects it. - -> [!say] For the follow-up I'll use a different building block: given one diagonal, the other two corners are fixed: the midpoint plus or minus the diagonal vector rotated by ninety degrees, halved. Doubling all coordinates keeps it in integers. - -> [!say] With floating-point coordinates I'd compare within a tolerance that scales with both the size of the figure and the magnitude of the coordinates, because the coordinates themselves carry rounding error proportional to their size.