LeetCode 1401. 圆和矩形是否有重叠
题目描述
题意分析
判断圆形区域与轴对齐矩形是否存在公共点，内部和边界都包含在内，所以相切也返回真。矩形横坐标范围为
[x1, x2]，纵坐标范围为[y1, y2]。
解法：几何最近点
核心思路
[!blue]
如果矩形中有点落在圆内，那么矩形中离圆心最近的点也一定落在圆内。反过来，若最近点已经在半径之外，其他点只会更远。因此只需求出这个最近点，再比较距离与半径。
点到圆心的距离平方为 $(x-xCenter)^2+(y-yCenter)^2$。矩形的横纵范围彼此独立，可以分别让两项达到最小，再将结果组合成同一个矩形内的点。
对一个坐标及其合法区间
[lo, hi]：坐标小于lo时，区间中最近的位置是lo；大于hi时最近的是hi；已经在区间内时，保留它就能让该方向距离为 0。这就是clamp的三个分支。分别处理圆心的横纵坐标，得到最近点(cx, cy)。令
dx = xCenter - cx、dy = yCenter - cy，判断dx * dx + dy * dy <= radius * radius即可。两边都是非负距离的平方，比较结果与开平方后相同，同时保持整数计算。圆心在矩形内部时，两方向距离都为 0，也会自然得到真。
解题步骤
- 分别求圆心坐标在横纵区间上的最近值。
- 计算两方向差的平方和。
- 与半径平方比较，包含等号。
代码实现
class Solution {
public boolean checkOverlap(
int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
// 轴对齐矩形的横纵范围独立，分别取离圆心最近的坐标。
int cx = clamp(xCenter, x1, x2);
int cy = clamp(yCenter, y1, y2);
int dx = xCenter - cx;
int dy = yCenter - cy;
// 最近点位于圆内或边界上时有交集，相切也算。
return dx * dx + dy * dy <= radius * radius;
}
private int clamp(int v, int lo, int hi) {
if (v < lo) {
return lo;
}
if (v > hi) {
return hi;
}
return v;
}
}
func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
// 轴对齐矩形的横纵范围独立，分别取离圆心最近的坐标。
cx := clamp(xCenter, x1, x2)
cy := clamp(yCenter, y1, y2)
dx := xCenter - cx
dy := yCenter - cy
// 最近点位于圆内或边界上时有交集，相切也算。
return dx*dx+dy*dy <= radius*radius
}
func clamp(v, lo, hi int) int {
if v < lo {
return lo
}
if v > hi {
return hi
}
return v
}
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 矩形轴对齐，两个坐标方向才能独立最小化。
- 最近点可能是内部、边中部或角点。
- 题面坐标在 $[-10^4,10^4]$ 内，两方向差的平方和至多为 $8\times10^8$，现有 32 位整数计算足够。
易错点总结
[!yellow]
- 只检查四角，会漏掉与边中部相切的情况。
- 只判断圆心在矩形内，会漏掉外部相交。
- 左边用平方距离、右边只用半径，会比较不同量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 836. 矩形重叠 | 简单 | 两题都判几何重叠，但矩形题要求正面积交集，本题最近点距离不超过半径时触边也算相交。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！