1. 先聊聊这道题到底在考什么
LeetCode 1401这道题，题目描述很直白：给你一个圆的圆心坐标和半径，再给你一个矩形的左下角和右上角坐标，判断圆和矩形是否有重叠。但题目越短，陷阱越多。我第一次交的时候，自信满满地写了一堆分情况讨论的if-else，结果WA了三次才过。后来回头看，才发现这题考的根本不是几何直觉，而是如何把一个看似复杂的空间关系问题，转换成一个足够简单、不容易出错的数学模型。
从面试角度来说，这道题属于“计算几何”里最基础的相交判断，但它常见的变形会出现在游戏开发里的碰撞检测、图形学里的裁剪算法，甚至机器人路径规划里的障碍物膨胀判断。所以别觉得它只是一道刷题工具题——理解了它的核心思想，你以后处理“图形A和图形B是否相交”这类问题会顺手很多
题目的数据范围也很友好，坐标和半径都是整数，绝对值不超过10^4。这意味着一个很关键的事情：大部分运算可以用整数完成，根本不需要碰浮点数。这点我后面会展开细说，因为“能用整数就不用浮点”是这类几何题里最容易踩坑，也最容易拿满分的一个优化点。
2. 核心思路拆解：别按直觉分区域，用“最近点”写法一劳永逸
2.1 从“圆和矩形重叠”翻译成数学条件
很多人的第一反应是分情况：圆在矩形左边、右边、上边、下边、四个角……然后每个方向单独判断圆和边的距离。这种思路没错，但代码会膨胀得很厉害，而且极易在“圆到底有没有压到角”这种边界上出错。
我推荐换一个角度想：圆和矩形重叠，等价于圆心到矩形区域的最短距离小于等于圆的半径。
这个“最短距离”怎么定义？分两种情况：
- 如果圆心在矩形内部（或者在边上），距离就是0，直接判重叠。
- 如果圆心在矩形外部，那最短距离就是圆心到矩形四条边所在的矩形边界的最近距离。
这样一翻译，问题就从“判断两个图形的相交关系”变成了“求一个点到矩形的最短距离”，后面这个在数学上是有闭式解的。而闭式解对应的代码非常干净，不需要写一堆if-else嵌套。
2.2 把矩形“压”到第一象限，思路瞬间清晰
这里有个使用频率极高的技巧：做坐标变换，把矩形中心平移到原点，再利用矩形的对称性把问题“折叠”到第一象限。
具体来说，矩形可以用它的半宽和半高来描述。假设矩形的左下角是(x1, y1)，右上角是(x2, y2)，那么：
- 中心点cx0 = (x1 + x2) / 2
- 中心点cy0 = (y1 + y2) / 2
- 半宽hx = (x2 - x1) / 2
- 半高hy = (y2 - y1) / 2
然后把圆心也做相对平移，得到相对于矩形中心的坐标(dx, dy) = (x - cx0, y - cy0)。
这时候，因为我们只关心“到矩形的最短距离”，而矩形关于中心点是中心对称的，所以可以直接取dx和dy的绝对值（或者说，把圆心按对称关系映射到第一象限）。
映射完之后的问题就极其简单了：第一象限里有一个以原点为中心的矩形，它的范围是[0, hx] × [0, hy]，圆心变成了第一象限里的某个点(|dx|, |dy|)，求这个点到这个矩形的最短距离。
2.3 关键步骤：把圆心“夹”到矩形边界上
现在到了最核心的一步。我们有了第一象限的矩形[0, hx] × [0, hy]，以及点(|dx|, |dy|)。怎么求点到矩形的最短距离？
答案就是一句话：把这个点“投影”到矩形内部最近的点上。
具体操作是三个clamp（钳位）操作：
- closestX = min(max(|dx|, 0), hx)
- closestY = min(max(|dy|, 0), hy)
换句话说，如果|dx|在0到hx之间，那最近点的x坐标就是|dx|本身；如果|dx|大于hx，最近点的x坐标就是hx；如果|dx|小于0，最近点的x坐标就是0。y方向同理。
然后求这个最近点(const closestX, closestY)到圆心(|dx|, |dy|)的距离的平方：
- distSq = (|dx| - closestX)^2 + (|dy| - closestY)^2
最后比较distSq和r^2。若distSq <= r^2，说明圆和矩形重叠。
这个思路最优雅的地方在于：不管是圆心在矩形内部、外部、还是正好在边界上，这三行clamp逻辑全部覆盖了，不需要任何额外的分支。
提示：为什么用平方距离而不是直接算距离？因为平方距离可以完全避免开根号操作，既省时间又避免浮点误差。在范围只有10^4的情况下，平方后的最大值是(2×10^4)^2 + (2×10^4)^2 = 8×10^8，用long long完全不会溢出。这是我推荐的第一优先级写法。
3. 两种主流解法的实现与对比
3.1 解法一：坐标变换 + 最近点法（推荐，代码极短）
先给出我最推荐的实现。这个方案把中心对称、取绝对值、clamp三步走完，代码短到让人怀疑是不是漏了什么。
以C++为例：
class Solution { public: bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { // 矩形中心 double cx = (x1 + x2) / 2.0; double cy = (y1 + y2) / 2.0; // 半宽半高 double hx = (x2 - x1) / 2.0; double hy = (y2 - y1) / 2.0; // 圆心相对矩形中心的坐标，取绝对值映射到第一象限 double dx = fabs(xCenter - cx); double dy = fabs(yCenter - cy); // 第一象限矩形范围是[0, hx] × [0, hy] // 把(dx, dy)钳位到矩形边界内部最近点 double closestX = min(max(dx, 0.0), hx); double closestY = min(max(dy, 0.0), hy); // 求最近点与圆心的距离平方 double distSq = (dx - closestX) * (dx - closestX) + (dy - closestY) * (dy - closestY); return distSq <= (double)radius * radius; } };这段代码的直观理解：先把矩形“压缩”成一个位于原点的对称图形，再利用对称性把问题限制到第一象限。此时矩形退化成一条从原点出发的“L形”边界，但我们依然用clamp的方式求最近点，逻辑完全一致。
注意：这里我使用了double，因为坐标是整数但中心可能是.5。如果你不想让代码里出现浮点数，可以把所有坐标都乘2，用整数运算，后面给方案二详细说明。
3.2 解法二：分区域讨论法（适合理解，但代码冗余）
另一种常见思路是直接把平面分成九个区域：矩形内部、四条边的外侧、四个角的外侧。这种思路符合直觉，适合用来向别人解释“为什么最近点法是对的”，但写代码时分支多，容易漏边界。
大致框架是这样的：
bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { // 圆心在矩形内部 if (xCenter >= x1 && xCenter <= x2 && yCenter >= y1 && yCenter <= y2) return true; // 圆在矩形左右两侧 if (xCenter < x1) { // 需要判断圆是否碰到左边这条边，同时还要考虑角上的情况 } // ... }你可以想象，这个写法需要处理的边界非常多。中心区域的判断还好，四个角上尤其容易出错：到底该用点到角点的距离，还是用点到边的距离？很多初学者写着写着就乱了。
所以我的建议很明确：**如果你只是为了解题，解法一永远是第一选择。**它的代码量只有分区域法的一半，而且本质上更接近“计算几何”这个领域的通用思维——只要你能把任意形状之间的关系转化成“点到区域的最短距离”问题，代码就会很简单。
3.3 整数运算技巧：完全避开浮点数的终极写法
前面提到，坐标和半径都是整数，这给了我们一个很大的优化空间：通过把坐标乘以2，可以完全避开浮点数。
具体做法是：在坐标变换时，不除以2，而是把圆心坐标也乘以2，然后所有距离判断都用整数完成。
class Solution { public: bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { // 所有坐标乘以2，避免浮点 long long r2 = 4LL * radius * radius; // 半径也乘2，所以平方后是4倍 long long cx = 1LL * (x1 + x2); // 矩形中心×2 long long cy = 1LL * (y1 + y2); // 矩形中心×2 long long hx = 1LL * (x2 - x1); // 矩形半宽×2 long long hy = 1LL * (y2 - y1); // 矩形半高×2 long long dx = llabs(2LL * xCenter - cx); long long dy = llabs(2LL * yCenter - cy); // clamp long long closestX = min(max(dx, 0LL), hx); long long closestY = min(max(dy, 0LL), hy); long long distSq = (dx - closestX) * (dx - closestX) + (dy - closestY) * (dy - closestY); return distSq <= r2; } };这个写法的好处是完全避开了浮点运算，彻底不存在精度问题。而且因为坐标范围很小，中间的乘法结果最大也就8×10^8，long long绰绰有余。
实操心得：我实际测下来，这个整数版本和浮点版本的耗时几乎没有差别（LeetCode这题的数据量太小，性能差异测不出来），但整数版本让人心里更踏实——毕竟浮点比较里distSq <= r^2这种判断，如果数值恰好相等，浮点误差可能让你多一次WA。整数写法直接消灭了这类不确定因素。
3.4 两种方案如何选：场景决定一切
如果你在面试中遇到这题，我建议先讲思路时用分区域法，因为面试官容易理解你的几何直觉；但真正写代码时直接上最近点法，边写边解释“这个写法统一了所有分支”。这样既展示了你能从几何角度理解问题，又展示了你能把数学结论转化为简洁代码的能力。
如果你只是自己刷题，那答案更简单：直接记住最近点法。它的代码量最小，出错的概率最低，而且更容易迁移到其他题型上——比如求圆和三角形、圆和多边形是否重叠，思路都是“求点到区域的最短距离”。
4. 复杂度分析与性能表现
4.1 时间与空间复杂度
这道题的时间复杂度是O(1)，因为我只做了有限的几次加减乘除和比较操作，与输入数据的大小无关。空间复杂度同样是O(1)，只用了几个临时变量。
复杂度虽然简单，但在解题报告里一定要写清楚，尤其是要说明“为什么是O(1)而不是O(n)”——因为这里没有任何遍历操作，数据规模是固定的输入参数（圆心坐标、半径、矩形坐标），算法只处理这些常量个数的数值。
4.2 “耗时100”是怎么做到的
LeetCode显示“耗时100%”的提交通常意味着代码运行时间进入了所有提交里的第一梯队。想做到这一点，代码本身要避免不必要的库函数调用和动态内存分配，当然更重要的是算法层面没有浪费操作。
我的整数版最终耗时确实能稳定排在100%，但说实话，这题的测试规模下，算法思想才是第一位，常数优化空间很小。真正让你“耗时100%”的不是某个魔法操作，而是你选择了一个根本没有多余操作的写法：不算开方、不调三角函数、不创建额外数据结构、不写一堆无意义的中间变量。
实操心得：如果你在LeetCode上看到耗时排名不是100%也别太纠结。本地测评机器负载波动、并发提交时间差，都会影响百分比。我更看重的是“代码无浮点、无分支冗余、无重复计算”这三点，做到这些，排名自然差不到哪去。
5. 边界条件与易错点盘点
5.1 圆和矩形“刚刚相切”算不算重叠
这是这题最微妙的地方。按照题目的定义，相切算重叠，因为重叠的定义是“有公共点”，而相切恰好有一个公共点。所以判断条件必须是distSq <= r^2，而不是distSq < r^2。
这个细节我在第一次提交时就踩坑了：我以为相切不算，写了严格小于，结果样例过不了。后来查题解才发现，题目的判定标准是“圆和矩形是否有重叠”，只要有一个点接触就算重叠。这个边界条件必须记住，面试时也经常被问到“相切你怎么处理”。
5.2 圆心恰好等于矩形中心点
当圆心和矩形中心完全重合时，dx = 0，dy = 0，closestX = 0，closestY = 0，distSq = 0。这时候只要半径>=0（半径肯定是正数），直接判重叠。这个case在最近点法里被统一处理了，不需要额外分支。
如果你用的是分区域法，这里也还好，因为圆心在矩形内部会直接返回true。但如果你写的是“至少距离某条边小于半径”这种判断，就要小心：圆心在矩形内部时，离四条边最近的距离也可能是0，必须和“圆心在矩形外部”的分支区分开，稍微不注意就漏了。
5.3 圆心恰好在矩形边上
如果圆心在矩形边上，比如恰好xCenter == x1且yCenter在y1和y2之间，那dx或dy就会等于hx或hy，clamp之后距离是0，直接判重叠。这也是“圆心在矩形内部或边上就直接重叠”的情形，最近点法统一处理，不需要额外写“是否在边上”的判断。
5.4 防止溢出的细节
虽然题目给的范围是10^4，但在计算distSq时，如果直接用int存dx - closestX的结果再相乘，可能在某些变体题目里溢出（比如坐标范围扩大）。我的建议是：任何涉及平方运算的变量都声明为long long，这是成本最低的防御性编程。
我实测过，哪怕不乘2直接硬算（保持double版本），也不会溢出，但long long版本没有任何坏处，反而让代码更统一。
6. 常见问题排查与调试技巧
6.1 我的结果是WA，但看起来逻辑没错
出现这种情况时，我一般会把圆心坐标、矩形坐标直接打印出来，自己用草稿纸画个图。常见的原因有三个：一是相切时用了<而不是<=；二是分区域法漏掉了某个角上的情况；三是浮点数比较时用了==而不是<=。
针对调试，我建议把每个case的dx、dy、closestX、closestY都打印出来，手动算一遍距离平方，然后跟代码结果对比。你会发现大部分WA都是某个坐标在边界值时，clamp的结果和你预期的不一致。
6.2 我用了浮点数，但总觉得不稳
浮点误差在几何题里确实是个隐患。最经典的翻车场景是：理论上应该相切的两个图形，因为浮点误差算出距离平方等于 r^2 + 1e-9，然后被判定为不重叠。
规避方法就是前面说过的：整型化。把所有坐标乘2，所有运算都在整数域内做。如果你不想改代码，也可以把比较条件改成distSq <= r^2 + 1e-9，但我觉得这种“加epsilon”的写法治标不治本，不如直接整型化来得干净。
6.3 我不理解为什么要取绝对值
很多新手会卡在这一步。我换个方式解释：矩形是关于中心点对称的，所以圆心在矩形的左上角、右上角、左下角、右下角，本质上到矩形的距离是完全一样的。取绝对值就是把这四个角的情况全部“折叠”到右上角这一种情况来处理。
打比方说，你在教室里问“我离讲台最近的距离是多少”，无论你站在讲台的哪一侧，答案都等于“你站在第一象限的同学到讲台的距离”——因为教室是对称的。取绝对值就是把这个对称性利用到极致，让代码少写四分之三的分支。
6.4 如何验证我的代码是对的
除了提交LeetCode看判定结果，我强烈建议你多构造一些手写测试用例。比如：
- 圆完全在矩形内部（应该返回true）
- 圆完全在矩形外部且距离很远（应该返回false）
- 圆和矩形相切（应该返回true）
- 圆非常大，覆盖了整个矩形（应该返回true）
- 圆心在矩形角点正上方，半径很小（应该返回false）
我在本地用这五个case验证，基本能覆盖大部分逻辑错误。你甚至可以把分区域法和最近点法两个版本都写上，随机生成坐标对拍，确认两个版本输出一致——这是竞赛选手常用的“对拍策略”，非常管用。
7. 从这题出发：下一步你可以怎么练
7.1 相关题目的延伸脉络
做完1401之后，我建议你顺着两个方向继续练：
第一个方向是“点到图形的最短距离”，比如求点到线段的最短距离、点到三角形的最短距离。LeetCode上没有太多直接考察这点的题，但面试里常以“求一个点到多边形内部的距离”这类变形出现，思路完全相同，核心就是找到所有可能的最近点候选，然后取最小距离。
第二个方向是“图形相交判断”，比如让你判断两个矩形是否重叠、两个圆是否重叠、圆和三角形是否重叠。这些题都能归约到“距离比较”上来，你只要把一个图形上的点集合、另一个图形上的点集合之间的最小距离求出来，和某个阈值比较即可。
7.2 把这道题的思维用到工程里
我在实际项目里遇到过和这个题几乎一模一样的场景：有一个圆形传感器，需要判断它扫过的区域是否碰到了某个矩形的障碍物。当时的代码就是把“圆心到矩形的最短距离”这个函数独立出来，供多个模块复用。后来团队做碰撞检测优化，这个函数成了核心模块之一。
所以别小看这个看似简单的题，它背后的“距离场”（distance field）思想在图形学、机器人、游戏AI里都是基础。理解了最近点，你就理解了“如何把一个几何问题变成数值问题”，这条思路能解决很多看起来无从下手的几何问题。
7.3 刷题先后顺序的参考
如果你是按LeetCode热门100题的顺序刷，遇到这种计算几何题时可以先跳过，把重点放在字符串、树、动态规划上。但如果你的目标是面试中的“系统设计 + 算法”双轮考核，这种几何题反而是容易拿分的点——因为套路固定、代码量小、不容易出错，而且面试官一看到你用最近点法而不是分区域法，会觉得你对计算几何有真实的理解。
我个人建议的顺序是：先刷完数组、链表、二叉树这类基础题，给自己建立信心，然后再集中攻克几何题。1401作为几何题的入门，性价比非常高，值得花半小时彻底搞懂。
7.4 最后分享一个我踩过的坑
这题我第一次提交时写了分区域法，自测全过，兴冲冲提交结果WA。查了很久发现，问题出在“圆心在矩形左边且半径足够大，碰到矩形左上角”这个case上——我的代码只判断了圆心到左边这条垂直线段的距离，忘了判断到左上角这个角点的距离。这个错误特别隐蔽，因为大多数自测用例都不会精确构造“圆在角的外侧但刚好碰到角”的情况。
后来用最近点法重写，这个bug就不存在了，因为clamp操作天然把角点的判断统一进去了。这个经历让我彻底改变了对待几何题的习惯：能用数学归结法解决的问题，绝不用几何分支法。分支越多，越容易漏；归结成公式，代码短，逻辑也更容易被验证。希望你也能从这个教训里受益。
