LeetCode 1401. 圆和矩形是否有重叠

2026-06-25 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 1401. 圆和矩形是否有重叠

题意分析

给出一个圆（半径 radius，圆心 (xCenter, yCenter)）和一个轴对齐矩形（左下角 (x1, y1)，右上角 (x2, y2)），判断两者是否存在公共点。这里的圆和矩形都是实心区域（包含边界），所以圆完全套住矩形、矩形完全套住圆、以及仅仅边缘相切，都算作有重叠。

「轴对齐」是最关键的信号：矩形可以拆成 $x \in [x_1, x_2]$ 与 $y \in [y_1, y_2]$ 两个互相独立的一维区间，横纵坐标的处理可以完全解耦，不需要做任何旋转或叉积。

所有输入都是整数，且 radius、坐标绝对值都在 $10^4$ 量级。整数输入是在提示：全程用整数平方距离比较，不要开方，既避免浮点误差也避免精度陷阱。同时 $dx^2 + dy^2$ 最大约 $2 \times (2 \times 10^4)^2 = 8 \times 10^8$，仍在 32 位整型范围内，不必升 long。

边界情形要想清楚三类：圆心落在矩形内部（必然重叠，无论半径多小）；圆与矩形边或角相切（距离恰等于半径，题目算重叠，所以比较符必须取 <=）；矩形整体落在圆内（离圆心最近的那个点也在圆内，判据依然成立）。

解法：几何最近点

核心思路

最朴素的想法是分情况讨论：圆心在矩形内、在矩形四条边的正对区域、在四个角的斜对区域……一共九个区域各写一套判断，再加上四个角点到圆心的距离比较。瓶颈不在时间而在正确性——九宫格分类极易漏写或写反某一格，白板上几乎必错。

突破口是把「两个区域是否相交」转化成「矩形上离圆心最近的那个点，到圆心的距离是否不超过半径」。这个等价性是双向的：若最近点距离 $\le r$，该点同时属于矩形和圆，自然相交；若存在任何公共点 $p$，那么 $p$ 到圆心的距离 $\le r$，而最近点的距离不会比 $p$ 更大，所以最近点距离也 $\le r$。于是判定问题被压成一次距离计算。

接下来要 $O(1)$ 求出这个最近点。轴对齐让 $x$ 与 $y$ 两维彻底独立：矩形是集合 ${(x,y) : x_1 \le x \le x_2,\ y_1 \le y \le y_2}$，而欧氏距离平方是 $(x - x_c)^2 + (y - y_c)^2$ 两项之和，两项分别只依赖一个变量，所以可以各自独立最小化。一维上，区间 $[lo, hi]$ 内离定点 $v$ 最近的点就是把 $v$ 截断（clamp） 到区间里：$v < lo$ 取 $lo$，$v > hi$ 取 $hi$，否则取 $v$ 本身。

于是得到本解法的核心定义：最近点 $(cx, cy) = (\mathrm{clamp}(x_c, x_1, x_2),\ \mathrm{clamp}(y_c, y_1, y_2))$，判据为 $(x_c - cx)^2 + (y_c - cy)^2 \le r^2$。这一个式子自动覆盖了前面说的九种区域：圆心在矩形内时两维都不截断，$cx = x_c$、$cy = y_c$，距离为 $0$ 必然成立；圆心在某条边的正对方向时只截断一维，退化为点到直线段的垂直距离；圆心在角的斜对方向时两维都被截断，$(cx, cy)$ 正好是那个角点。

解题步骤

对横坐标做截断 cx = clamp(xCenter, x1, x2)。为什么截断就是最近：距离平方关于 $x$ 是开口向上的抛物线，顶点在 $x_c$，在区间 $[x_1, x_2]$ 上的最小值必然取在顶点或离顶点最近的端点，这正是截断的定义。

对纵坐标做同样的截断 cy = clamp(yCenter, y1, y2)。两维能分开做，靠的是矩形轴对齐这一条——如果矩形是斜的，$x$ 的可行范围会依赖 $y$，解耦就不成立了。

算 dx = xCenter - cx、dy = yCenter - cy，即圆心到最近点的两个分量。不用取绝对值，因为下一步要平方。

返回 dx * dx + dy * dy <= radius * radius。比较平方而非距离本身，是因为平方保序（两边都非负）且能全程停留在整数域，彻底规避 Math.sqrt 的浮点误差；比较符必须是 <=，相切按题意算重叠。

以 radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1 走一遍：

截断横坐标：$x_c = 0$ 小于 $x_1 = 1$，所以 cx = 1。
截断纵坐标：$y_c = 0$ 落在 $[-1, 1]$ 内，不截断，cy = 0。
分量：dx = 0 - 1 = -1，dy = 0 - 0 = 0。
判据：$(-1)^2 + 0^2 = 1$，$r^2 = 1$，$1 \le 1$ 成立，返回 true。几何上圆心在矩形左侧正对区域，圆恰好与矩形左边 $x = 1$ 相切于点 $(1, 0)$，属于「相切算重叠」的边界情形。

再以 radius = 1, xCenter = 1, yCenter = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3 走一遍：$x_c = 1$ 在 $[-3, 3]$ 内、$y_c = 1$ 也在 $[-3, 3]$ 内，两维都不截断，cx = 1、cy = 1，dx = dy = 0，距离平方 $0 \le 1$，返回 true——圆心在矩形内部，最近点就是圆心自己，这一支不需要任何特判就被主逻辑覆盖了。

代码实现

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)$。只用了 cx、cy、dx、dy 四个整型局部变量，没有任何与输入规模相关的分配。

关键点总结

判断两个凸区域是否相交，等价于判断「一个区域上离另一个区域最近的点」是否落入后者。把「是否存在公共点」这个存在性问题转成「最优点是否满足条件」的最优化问题，是计算几何里最常复用的降维手法。

轴对齐意味着维度可分离：目标函数写成各维之和、可行域写成各维区间的笛卡尔积时，就能逐维独立求最优，$k$ 维问题拆成 $k$ 个一维问题。

一维上「区间内离定点最近」永远是 clamp，这个小工具能一举替代边、角、内部的九宫格分类讨论，代码短且没有遗漏分支。

距离比较一律用平方形式。输入是整数时平方保持整数，既没有浮点误差也没有 sqrt 的开销；只要注意平方后是否溢出，本题最大约 $8 \times 10^8$，int 足够。

面试视角：面试官想看你能不能避开分类讨论。开口先说「我不做九宫格，我求矩形上到圆心的最近点」，再解释 clamp 的正确性和平方比较的动机，基本就满分了。追问「如果矩形不是轴对齐呢」要能答出：把圆心变换到矩形的局部坐标系（旋转 $-\theta$）后仍然可以 clamp，因为旋转是保距变换。

易错点总结

判断符写成 <：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1 时距离平方恰为 $1$，用 < 会返回 false，而相切按题意算重叠，正确是 true。

只比较圆心到四个角点的距离：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -5, x2 = 3, y2 = 5 时四个角点距圆心都远超 $1$，会错答 false，实际圆与左边中段相切，正确是 true。

只判断圆心是否在矩形内：radius = 5, xCenter = 0, yCenter = 0, x1 = 1, y1 = 1, x2 = 2, y2 = 2 时圆心在矩形外，会错答 false，实际矩形整体被圆包住，正确是 true。

只判断矩形四角是否在圆内：radius = 1, xCenter = 0, yCenter = 0, x1 = -5, y1 = -5, x2 = 5, y2 = 5 时四个角点距圆心都是 $\sqrt{50}$ 远超半径，会错答 false，实际圆完全在矩形内，正确是 true。

用 Math.sqrt 求距离再与 radius 比较：radius = 5, xCenter = 0, yCenter = 0, x1 = 3, y1 = 4, x2 = 9, y2 = 9 时最近点是角点 $(3, 4)$，真实距离恰为 $5$，而 Math.sqrt(25) 在某些实现下返回 4.999999999999999，等号被判成小于失败，返回 false，正确是 true。

截断时把 lo、hi 传反：写成 clamp(xCenter, x2, x1)，在 x1 = 1, x2 = 3, xCenter = 0 时先判 $0 < 3$ 返回 $3$，最近点取成了远端，距离平方变成 $9 > 1$，错答 false。

误以为 x1 < x2 不成立需要先交换：题目保证 x1 < x2 且 y1 < y2，额外加交换逻辑不会出错但属多余；真正危险的是反过来假设输入可能是右上角在前而写死了 clamp(v, hi, lo)。

把 radius * radius 写成 radius 忘记平方：radius = 3, xCenter = 0, yCenter = 0, x1 = 2, y1 = 0, x2 = 4, y2 = 1 时距离平方为 $4$，与未平方的 $3$ 比较得 false，正确是 true。

两维只截断一维：只对 $x$ 截断而直接用 yCenter，在 radius = 1, xCenter = 0, yCenter = 10, x1 = -1, y1 = -1, x2 = 1, y2 = 1 时 dy 算成 $0$，距离平方为 $0$，错答 true，正确是 false。

相似题目

题目	难度	考察点
836. 矩形重叠	简单	两个轴对齐矩形相交，同样逐维独立判断，但只需区间是否有交而无需求最近点
223. 矩形面积	中等	从判相交进一步到算重叠面积，需逐维求交集长度再做容斥
593. 有效的正方形	中等	同样用平方距离避开开方，靠六条边长的多重集特征而非区域相交
973. 最接近原点的 K 个点	中等	同为平方距离比较，重点转为 Top-K 选取，需堆或快速选择
56. 合并区间	中等	一维区间相交的批量版本，需排序后线性扫描合并
435. 无重叠区间	中等	一维相交判定用于贪心决策，按右端点排序移除最少区间
850. 矩形面积 II	困难	多矩形并集面积，需扫描线加线段树，逐维解耦升级为按 $x$ 扫描离散化的 $y$ 轴
391. 完美矩形	困难	判断多个矩形是否恰好拼成一个大矩形，靠面积和与角点奇偶计数