LeetCode 面试题 16.13. 平分正方形
目录
题目描述
题意分析
每个正方形用
[x, y, size]表示，(x, y)是左下角，边与坐标轴平行。要返回一条同时把两个正方形面积平分的直线在两个正方形并集上的两个最远交点，格式为[x1, y1, x2, y2]；端点按 x 升序，x 相同再按 y 升序。正方形是中心对称图形，任何经过中心的直线都会把它分成面积相等的两半。因此问题的真正约束不是“算面积”，而是找一条同时经过两个中心的直线。两个中心不重合时直线唯一；中心重合时合法直线有无穷多，选竖直线即可得到稳定答案。
还要决定直线从正方形的哪组边穿出。斜率绝对值不大于 1 时，横向变化更快，交点落在左右边；绝对值大于 1 时，交点落在上下边。竖直线必须单独处理，不能先算斜率。
解法：中心连线 + 按斜率选择边界
核心思路
两个中心分别是
(cx1, cy1)、(cx2, cy2)。若cx1 = cx2，直接取共同 x，y 从两个正方形的最低边延伸到最高边。否则直线写成
y = kx + b，其中k = (cy2 - cy1) / (cx2 - cx1)。核心不变量是：返回的两个端点始终在这条中心连线上，并且分别位于沿直线方向能覆盖两个正方形的最外侧边界。当
|k| <= 1时，用两个正方形最小的左边界作为x1、最大的右边界作为x2，再代入直线求 y；当|k| > 1时，用最低下边界与最高上边界作为 y，再反解 x。陡峭且为负斜率时，按 y 取出的两个点可能 x 逆序，最后按题目规则交换即可。这比枚举四条边求所有交点更短：中心对称性先把候选直线压成一条，斜率大小再把四种边界压成一组。
解题步骤
- 用浮点除法计算两个中心，边长除以 2 时不能做整数除法。
- 若中心 x 相同，返回
[cx, minBottom, cx, maxTop]。- 计算
k与b。- 若
|k| > 1，取全局最低、最高 y，分别由x = (y - b) / k求 x。- 否则取全局最左、最右 x，分别由
y = kx + b求 y。- 陡斜率分支按 x、y 的字典序整理端点。
例：
square1 = [-1,-1,2]、square2 = [2,1,2]。中心是(0,0)与(3,2)，所以k = 2/3、b = 0，属于左右边分支。最左 x 为 -1，最右 x 为 4，代入得到端点(-1,-2/3)与(4,8/3)。两点都在中心连线上，线段也覆盖了两个正方形。
代码实现
class Solution {
public double[] cutSquares(int[] square1, int[] square2) {
double x1 = square1[0] + square1[2] / 2.0;
double y1 = square1[1] + square1[2] / 2.0;
double x2 = square2[0] + square2[2] / 2.0;
double y2 = square2[1] + square2[2] / 2.0;
if (x1 == x2) {
double y3 = Math.min(square1[1], square2[1]);
double y4 = Math.max(square1[1] + square1[2], square2[1] + square2[2]);
return new double[] {x1, y3, x2, y4};
}
double k = (y2 - y1) / (x2 - x1);
double b = y1 - k * x1;
if (Math.abs(k) > 1) {
double y3 = Math.min(square1[1], square2[1]);
double x3 = (y3 - b) / k;
double y4 = Math.max(square1[1] + square1[2], square2[1] + square2[2]);
double x4 = (y4 - b) / k;
if (x3 > x4 || (x3 == x4 && y3 > y4)) {
return new double[] {x4, y4, x3, y3};
}
return new double[] {x3, y3, x4, y4};
} else {
double x3 = Math.min(square1[0], square2[0]);
double y3 = k * x3 + b;
double x4 = Math.max(square1[0] + square1[2], square2[0] + square2[2]);
double y4 = k * x4 + b;
return new double[] {x3, y3, x4, y4};
}
}
}
func cutSquares(square1 []int, square2 []int) []float64 {
x1, y1 := float64(square1[0])+float64(square1[2])/2, float64(square1[1])+float64(square1[2])/2
x2, y2 := float64(square2[0])+float64(square2[2])/2, float64(square2[1])+float64(square2[2])/2
if x1 == x2 {
y3 := math.Min(float64(square1[1]), float64(square2[1]))
y4 := math.Max(float64(square1[1]+square1[2]), float64(square2[1]+square2[2]))
return []float64{x1, y3, x2, y4}
}
k := (y2 - y1) / (x2 - x1)
b := y1 - k*x1
if math.Abs(k) > 1 {
y3 := math.Min(float64(square1[1]), float64(square2[1]))
x3 := (y3 - b) / k
y4 := math.Max(float64(square1[1]+square1[2]), float64(square2[1]+square2[2]))
x4 := (y4 - b) / k
if x3 > x4 || (x3 == x4 && y3 > y4) {
return []float64{x4, y4, x3, y3}
}
return []float64{x3, y3, x4, y4}
} else {
x3 := math.Min(float64(square1[0]), float64(square2[0]))
y3 := k*x3 + b
x4 := math.Max(float64(square1[0]+square1[2]), float64(square2[0]+square2[2]))
y4 := k*x4 + b
return []float64{x3, y3, x4, y4}
}
}
复杂度分析
- 时间复杂度：
O(1)，只做固定次数的算术与比较。- 空间复杂度：
O(1)，返回数组之外只使用常数个浮点变量。
关键点总结
- “平分正方形”首先想到中心对称，而不是积分或多边形裁剪。
|k| <= 1取左右边，|k| > 1取上下边，保证算出的点确实落在边界上。- 竖直线独立处理，既规避除零，也覆盖两个中心重合的退化情况。
- 面试追问通常是“为什么过中心一定平分”和“浮点比较是否安全”。前者用中心对称一一配对解释；本题中心来自整数或半整数，
x1 == x2可精确比较，其他结果按浮点误差容忍判定。
易错点总结
- 错误写法：连接两个正方形的某两个角。反例两个正方形上下错位时，角点连线一般不经过中心，切出的两块面积不相等。
- 先统一计算斜率：当两个中心 x 相同会除以 0；例如
[0,0,2]与[0,3,2]应返回竖直线x = 1。- 无论斜率都取左右边：水平跨度很小、
|k| > 1时算出的 y 会落在正方形上下边之外。陡直线必须改取上下边。- 中心写成
x + size / 2的整数运算：边长为奇数时中心被截断。例如[0,0,1]的中心应为(0.5,0.5)，错算成(0,0)会改变整条直线。- 负斜率不整理端点：上下边分支可能先得到 x 较大的点，违反题目要求的端点顺序。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 直线表示与斜率归一化 |
| 1232. 缀点成线 | 简单 | 叉积判共线，避免浮点斜率 |
| 593. 有效的正方形 | 中等 | 用距离刻画正方形几何约束 |