看到“leetcode 1401. Circle and Rectangle Overlapping —— 圆和矩形是否有重叠耗时100”这个标题估计不少人心里会嘀咕一道几何判断题AC不就行了盯着耗时是不是有点钻牛角尖。但刷题到后面你会发现Runtime分布其实是个很诚实的信号——同样AC的代码分支多不多、有没有浮点运算、常数是大是小分布上能拉开明显差距。1401这道题我前后写过两个版本第一版规规矩矩按九宫格分情况讨论四十多行代码调边界调到头秃第二版换成“找矩形上离圆心最近的点”这个思路核心逻辑三行写完耗时也自然落在前排。这篇不打算只贴个答案而是把题意、原理、最优写法、边界坑全部讲清楚顺便聊聊为什么有的写法天生就慢。适合正在刷LeetCode准备面试的读者也适合对计算几何感兴趣的朋友哪怕只有高中数学基础也跟得上。1. 题意拆解三种重叠情形里藏着解题钥匙题目说的是给一个圆的圆心坐标和半径再给一个轴对齐矩形四条边分别平行于 x 轴和 y 轴的左下角坐标、右上角坐标判断圆和矩形有没有重叠。注意“轴对齐”三个字极其关键它意味着矩形本质上就是x 区间 [x1, x2] 和 y 区间 [y1, y2] 的笛卡尔积。这个观察是后面所有推导的地基。“重叠”这个词在本题里包含相切。画个图就明白圆和矩形只要交集非空就算重叠哪怕只是刚好擦到一条边或者一个顶点。很多人第一次做这题就挂在符号上最后判断写了而不是遇到刻意构造的相切用例直接 WA 一次。这不是粗心是对定义不够较真。把重叠的所有可能性列一遍其实只有三类情形。第一类圆心落在矩形内部包括边界上。这时候圆心本身既是圆上的点又落在矩形内交集显然非空直接判定重叠。这一条最朴素但也是很多人写代码时唯一能稳拿的分。第二类圆心在矩形外部但圆和矩形某条边相交。例如矩形是 [0,10]×[0,10]圆心在 (13,5)半径 3圆会碰到 x10 这条右边。此时圆心到这条边的垂足恰好落在边线段上且垂足到圆心的距离不超过半径。第三类圆心在矩形外部而且位于某个角的斜对角方向。比如圆心在 (13,13)矩形还是 [0,10]×[0,10]它到矩形最近的点是顶点 (10,10)距离是 √18这时候判断依据应该是顶点距离而不是到哪条边所在直线的垂距。第一次做这题时我脑子里冒出来的方案是把矩形的四条边无限延长整个平面会被切成九个区域然后数一数圆心落在哪个区域。中间区域直接重叠上下左右四个侧区域看边垂距四个角落区域看顶点距离。这个思路完全正确九宫格分类本质上就是把这三种情形掰开揉碎。但我把它写成代码之后发现到处都是 if 和 else 的组合区域边界要不要取等号、垂足是否落在线段内、角落区域怎么和侧边区域区分……四十多行代码调试了大半天最后 AC 了也心里发虚。其实这道题的钥匙不是“分几种情况”而是换一个问题圆和矩形是否重叠等价于圆心到矩形的最近距离是否不大于半径。证明非常直接如果圆和矩形有交集那么交集里的那个点到圆心的距离必然不超过半径所以圆心到矩形的最近距离也不超过半径反过来如果圆心到矩形的最近点距离不超过半径那么这个最近点本身就在圆内交集非空。想通这一层剩下的问题就只有一个了怎么求一个点到矩形的最近距离。当时我还注意到一个细节题目给的数据全是整数半径和所有坐标的范围都在 -10^4 到 10^4 之间。这个条件意味着整道题可以完全避开浮点运算这也是后面“耗时100”的重要前提之一。2. 区间夹取法把二维矩形压缩成两段数轴的数学原理既然矩形是 axis-aligned 的那么“点到矩形的最近距离”就可以拆成两个独立的一维问题。这里的核心操作叫clamp夹取函数定义很简单如果 v 小于下界 lo返回 lo如果 v 大于上界 hi返回 hi否则返回 v 本身。一句话总结把 v 推到区间 [lo, hi] 里离它最近的位置。于是矩形上距离圆心 C(cx, cy) 最近的点 P 可以写成P ( clamp(cx, x1, x2), clamp(cy, y1, y2) )很多读者看到这里会怀疑凭什么能把 x 和 y 分开算万一 x 方向的选取会影响 y 方向的最优解怎么办这个问题问得非常好答案藏在距离公式里。圆心到矩形上任意一点 Q(x, y) 的距离平方是(cx - x)^2 (cy - y)^2这是一个“可分离变量”的函数x 只出现在第一项y 只出现在第二项两项相加。求它在矩形上的最小值等价于分别在 x∈[x1,x2] 和 y∈[y1,y2] 上最小化两个独立的一维函数min (cx-x)^2以及 min (cy-y)^2而 (c-t)^2 是开口向上的二次函数它在闭区间上的最小值点只有三种情况对称轴 tc 落在区间内就取 c 本身对称轴在区间左边就取区间左端点对称轴在区间右边就取区间右端点。这三种情况合起来恰好就是 clamp 干的活。有了最近点 P判定就变成了一个平方距离比较(cx-px)^2 (cy-py)^2 radius^2请注意这里故意不开根号原因后面代码部分会展开说。这个 clamp 公式和九宫格分类是一一对应的圆心在矩形内部时clamp 原样返回 cx 和 cyP 就是圆心距离 0圆心在矩形左侧或右侧时x 被压到最近的边界y 保持原样P 就是垂足圆心在角外区域时x 和 y 同时被压到边界上P 自动变成角点。所以完全可以把 clamp 看成“一次算完九种情况”的闭式表达九宫格写法只是它的显式展开。我还想强调一个更通用的几何结论对任何封闭凸体判断一个圆是否与它相交等价于判断圆心到它的距离是否不超过半径。圆本身是凸集封闭凸体的最近点又一定存在所以这个双向论证几乎可以无脑套用。以后遇到圆和三角形、圆和平行四边形、圆和半平面之类的问题主线思路都不用换。顺便说一句有些题解在求最近距离时绕远路比如枚举矩形边上的采样点或者拿画圆的 Bresenham 算法逐点判断都属于把 O(1) 的题硬做成 O(直径) 甚至 O(面积)。一旦理解“最近点距离法”这类低效方案应该一眼就被排除掉。3. 耗时100的写法长什么样完整代码与逐行拆解下面以 Python 为例给出我最终在 LeetCode 上提交的版本。题目保证输入全是整数所以全程整数运算不需要碰浮点class Solution: def checkOverlap( self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int ) - bool: px max(x1, min(x2, xCenter)) py max(y1, min(y2, yCenter)) dx, dy xCenter - px, yCenter - py return dx * dx dy * dy radius * radius有效逻辑只有五行逐行拆开说。px max(x1, min(x2, xCenter))这一行是嵌套 clamp。min(x2, xCenter)先保证 xCenter 不越过右边界外层max(x1, ...)再保证不越过左边界。写成min(x2, max(x1, xCenter))也完全等价在 x1 x2 的前提下两种顺序结果一样。我自己习惯用max(lo, min(hi, v))读起来是“先压上限、再提下限”不太容易把 lo 和 hi 写反。py 同理对 yCenter 做一次一维夹取。dx, dy是圆心到最近点 P 的两个分量。最后比较距离平方与半径平方。为什么不开根号因为距离比较在平方意义下是等价的a b 当且仅当 a^2 b^2a、b 都是非负数。开根号不仅多一次浮点运算还可能引入精度误差完全没必要。只要半径和坐标里没有小数整数平方就是最安全、最省事的路径。这段代码跑出来耗时确实能落在较靠前的位置。但说句公道话LeetCode 的 runtime 本身波动很大同一份代码不同时间提交可能差出三五十毫秒服务器负载、语言版本都会影响结果。所以“耗时100”这个数字不用神化重点是这份代码确实把常数压到了很低不碰浮点、没有分支、没有递归、没有额外数组只有几次整数加减乘和比较。对比一下我一开始写的 if-else 版本也许你更能体会差距class Solution: def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) - bool: if x1 xCenter x2 and y1 yCenter y2: return True if xCenter x1 and y1 yCenter y2: return (x1 - xCenter) ** 2 radius * radius if xCenter x2 and y1 yCenter y2: return (xCenter - x2) ** 2 radius * radius if yCenter y1 and x1 xCenter x2: return (y1 - yCenter) ** 2 radius * radius if yCenter y2 and x1 xCenter x2: return (yCenter - y2) ** 2 radius * radius dx max(x1 - xCenter, 0, xCenter - x2) dy max(y1 - yCenter, 0, yCenter - y2) return dx * dx dy * dy radius * radius这个版本也能 AC但你看它维护了多少个区域条件。中间那五个 if 其实全是多余的角落情况的 max 公式已经能覆盖所有“圆心在矩形外部”的场景。每多一个分支就多一个出错点比如第三个条件里 yCenter 等于 y1 时它既算“圆心在下方”的边界又算“圆心在矩形内部”的边界两个 if 都可能命中逻辑虽然没错读起来却让人心里不踏实。如果你用 C 刷题C17 以后可以直接用标准库的std::clampclass Solution { public: bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { int px std::clamp(xCenter, x1, x2); int py std::clamp(yCenter, y1, y2); long long dx xCenter - px, dy yCenter - py; return dx * dx dy * dy 1LL * radius * radius; } };这里我把 dx、dy 声明成 long long属于求稳的做法。题目数据范围下 int 其实装得下坐标绝对值不超过 10^4dx、dy 最大 2×10^4平方和最大约 8×10^8半径最大 10^4平方 10^8加一起也远小于 32 位 int 的上限。但写上 long long 不花任何代价还让读代码的人不用心算溢出边界。复杂度结论很简单时间 O(1)空间 O(1)。没有遍历、没有排序、没有二分一次 clamp 加一次平方比较就收工。4. 边界条件清单六个容易做错的反例免费送几何题的隐藏分基本都在边界条件里。以下六个测试用例每一个都对应一类经典错误建议直接抄进本地自测脚本。第一个相切必须算重叠。矩形 [0,10]×[0,10]圆心 (10,5)半径 5。圆与右边界在 (10,5) 处相切结果必须是 true。如果你最后用的是而不是这个用例直接挂掉。这个坑最隐蔽因为平时写“小于”写习惯了容易忘了“相切也是相交”。第二个圆心在矩形内部时必然重叠。矩形 [0,10]×[0,10]圆心 (5,5)半径 1。clamp 之后 px5, py5距离平方为 0必然 true。这个用例主要用来验证 clamp 在最内层的正确性如果哪里把 x1 和 x2 写反了这里立刻现原形。第三个圆心在边的外侧但垂足落在边的延长线上。矩形 [0,5]×[0,5]圆心 (6,-1)半径 1。如果按“圆心到直线 x5 的距离”去判断距离是 1会误判为重叠但真正的最近矩形点是 (5,0)距离平方是 (6-5)^2 (-1-0)^2 2所以不重叠。这个用例专治“拿垂距当最短距离”的错误clamp 法对它是天然免疫的因为 pyclamp(-1,0,5)0自动选到了 (5,0)。第四个负坐标照常工作。矩形 [-5,-1]×[-5,-1]圆心 (-3,-3)半径 1圆心在矩形内部显然重叠。换成圆心 (-10,-10)最近点变成 (-5,-5)距离平方 50 大于 1不重叠。clamp 是纯数值运算正负号不影响语义这个用例只是让你放心。第五个角部斜向距离。矩形 [0,10]×[0,10]圆心 (-3,-4)半径 6。最近点是 (0,0)距离平方是 25半径平方是 36重叠。半径改成 4则 25 大于 16不重叠。这个用例专门验证角外区域的 clamp 会不会给到顶点而不是某个虚构的垂足。第六个远距离冒烟测试。矩形 [0,10]×[0,10]圆心 (100,100)半径 1。最近点是 (10,10)距离平方 16200显然不重叠。用例本身没什么花头但它能快速暴露坐标写串、参数顺序颠倒之类的低级错误。场景示例输入期望结果容易踩的坑相切圆心(10,5)r5矩形[0,10]×[0,10]true用漏掉圆心在矩形内圆心(5,5)r1矩形[0,10]×[0,10]trueclamp 把坐标区间写反垂足在延长线上圆心(6,-1)r1矩形[0,5]×[0,5]false拿点到直线距离当最短距离负坐标圆心(-3,-3)r1矩形[-5,-1]×[-5,-1]true担心负数破坏逻辑角部斜向距离圆心(-3,-4)r6矩形[0,10]×[0,10]true误用垂足而不是顶点远距离圆心(100,100)r1矩形[0,10]×[0,10]falsex、y 坐标串位最后提醒一个输入约定题目保证 x1 x2、y1 y2所以不需要对矩形坐标做交换。clamp 代码如果依赖这个顺序就别顺手改成支持乱序输入否则逻辑会被悄悄改写。面试里遇到“输入不合法怎么办”的问题直接回答“按题目约束输入保证合法不额外处理”最干脆。另外如果哪天你在别的平台看到同题但坐标是浮点数的版本判断相等时需要加容差写成 radius * radius 1e-9。整数版不需要用足够。5. 从1401延伸这个思路能覆盖更多几何问题最后想聊聊这道题之外的东西。判断“圆和矩形是否重叠”在算法题里只是一个小点但“找最近点再比距离”这个模式能直接套到不少真实场景。在游戏开发和图形学里AABBAxis-Aligned Bounding Box轴对齐包围盒是最常用的碰撞检测包围体。判断一个圆是否撞进 AABB标准做法就是“closest point on AABB to point”给定包围盒左下角 (minX, minY) 和右上角 (maxX, maxY)把圆心坐标两边各 clamp 一次再比距离。这和 LeetCode 1401 的解法几乎逐字相同。如果你面的岗位涉及渲染、物理引擎、仿真这个函数完全可能出现在白板题里。再推广一步判断圆与任意线段是否重叠方法类似只是 clamp 的对象变成了线段参数 t。设线段端点 A、B对任意点 P先算向量 AP 在 AB 上的投影参数t ((P.x - A.x) * (B.x - A.x) (P.y - A.y) * (B.y - A.y)) / |AB|^2把 t 夹到 [0,1] 得到最近点的位置再算 P 到该点的距离。线段其实就是“一维 clamp 在二维空间里的几何体现”和矩形问题本质完全一致。再往外走一步判断圆与任意凸多边形是否重叠多边形没有“两个独立区间”这么好的性质那就遍历每条边算圆心到每条线段的最短距离取最小值再判断是否不超过半径。复杂度从 O(1) 变成 O(n)但主线没变仍然是找最近点、比较距离。这一个套路能覆盖一整个系列的计算几何题。回到日常刷题我从这道题里获得的最大收获其实不是那三行代码而是解题习惯上的转变。遇到几何题先问自己能不能把“物体相交”转化成“距离判断”遇到矩形先问自己能不能把它拆成独立的轴向区间。这两个问题问完很多看起来要分类讨论的题都会自动收敛到一条很短的路径。那次重构之后我写几何题的 if-else 数量明显变少了因为大部分分类逻辑都被 clamp、投影、距离公式这些更本质的运算吸收了。我的建议是把这道题的“最近点法”连同点到线段最短距离的函数一起存进代码笔记做成自己的几何模板。下次遇到计算几何题先看能不能用同一个思路解不行再考虑凸包、叉积、扫描线那些更重的工具。我个人的体会是计算几何题最忌讳一上来就分情况讨论能压缩的分类尽量压缩成闭式表达代码会短得多正确率也会高得多。