LeetCode 面试题 16.13. 平分正方形
题目描述
题意分析
每个正方形用
[x, y, size]表示，(x, y)是左下角，边与坐标轴平行。要返回一条同时把两个正方形面积平分的直线在两个正方形并集上的两个最远交点，格式为[x1, y1, x2, y2]；端点按 x 升序，x 相同再按 y 升序。正方形关于中心旋转半周后与自身重合，过中心直线两侧的部分恰好互相对应，所以面积相等。同方向的直线若平行移离中心，会把一块正面积区域从一侧划到另一侧，便不再平分。因此答案必须同时经过两个中心。
两个中心不同就确定唯一连线；中心重合时，任意过中心直线都合法，按题目“最大斜率”的约定选择竖直线。确定直线后，还要找出它与两个正方形形成的四个交点中最外侧的两个。
解法：中心连线 + 按斜率选择边界
核心思路
[!blue]
两个中心分别是
(cx1, cy1)、(cx2, cy2)。若cx1 = cx2，直接取共同 x，y 从两个正方形的最低边延伸到最高边。否则直线写成
y = kx + b，其中k = (cy2 - cy1) / (cx2 - cx1)、b = cy1 - k * cx1。只需判断它先碰到左右边还是上下边，无需逐边枚举交点。设某个正方形的半边长为
h。从中心向左右边移动h时，纵向变化为|k| * h。若|k| <= 1，纵向变化没有超过半边长，所以交点确实落在左右边上；相等时恰好经过角点。两个正方形都适用这个判断，因此取全局最小左边界和最大右边界作为两个 x，再代入直线求 y，就得到最外侧端点。若
|k| > 1，到达上下边时横向变化只有h / |k| < h，因此改取全局最低下边界和最高上边界作为两个 y，再用x = (y - b) / k反解 x。直线上点的顺序可由任一非恒定坐标表示，这样取得的两个极值点之间一定包含另外两个交点，两个正方形重叠或相隔也不影响结论。竖直分支已按 y 从小到大返回，左右边分支已按 x 从小到大返回。上下边分支在负斜率时可能得到 x 逆序，因此最后按 x 优先、y 次之的顺序交换端点。
解题步骤
- 用浮点除法计算两个中心，边长除以 2 时不能做整数除法。
- 若中心 x 相同，返回
[cx, minBottom, cx, maxTop]。- 计算
k与b。- 若
|k| > 1，取全局最低、最高 y，分别由x = (y - b) / k求 x。- 否则取全局最左、最右 x，分别由
y = kx + b求 y。- 陡斜率分支按 x、y 的字典序整理端点。
代码实现
class Solution {
public double[] cutSquares(int[] square1, int[] square2) {
double x1 = (double) square1[0] + square1[2] / 2.0;
double y1 = (double) square1[1] + square1[2] / 2.0;
double x2 = (double) square2[0] + square2[2] / 2.0;
double y2 = (double) square2[1] + square2[2] / 2.0;
if (x1 == x2) {
double y3 = Math.min(square1[1], square2[1]);
double y4 =
Math.max((double) square1[1] + square1[2], (double) 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((double) square1[1] + square1[2], (double) 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((double) square1[0] + square1[2], (double) square2[0] + square2[2]);
double y4 = k * x4 + b;
return new double[] {
x3,
y3,
x4,
y4
};
}
}
}
import (
"math"
)
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])+float64(square1[2]), float64(square2[1])+float64(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])+float64(square1[2]), float64(square2[1])+float64(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])+float64(square1[2]), float64(square2[0])+float64(square2[2]))
y4 := k*x4 + b
return []float64{
x3,
y3,
x4,
y4,
}
}
}
复杂度分析
- 时间复杂度：
O(1)，只做固定次数的算术与比较。- 空间复杂度：
O(1)，返回数组之外只使用常数个浮点变量。
关键点总结
[!green]
- “平分正方形”首先想到中心对称，而不是积分或多边形裁剪。
|k| <= 1取左右边，|k| > 1取上下边，保证算出的点确实落在边界上。- 竖直线独立处理，既规避除零，也覆盖两个中心重合的退化情况。
- 中心由整数或半整数组成，代码先转为浮点数再计算，中心横坐标是否相同可以直接比较。
易错点总结
[!yellow]
- 连接任意两个角：角点连线不一定经过两个中心，不能保证平分面积。
- 先统一计算斜率：两个中心 x 相同时会除以 0，应先处理竖直线。
- 无论斜率都取左右边：水平跨度很小、
|k| > 1时算出的 y 会落在正方形上下边之外。陡直线必须改取上下边。- 中心写成
x + size / 2的整数运算：奇数边长的半整数中心会被截断，改变整条直线。- 计算右边界或上边界前先转换为浮点数，不能让两个 int 先相加溢出后再转换。
- 负斜率不整理端点：上下边分支可能先得到 x 较大的点，违反题目要求的端点顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 同样处理平面直线，本题由两个中心唯一确定候选，原题对多点统计共线数量。 |