分治算法经典：最近点对问题全解析，O(n log n)高效解法与C++实现

最近点对问题是我接触分治算法时觉得最“惊艳”的一道题题号3354教材例61.2题目就一句话给定平面上 n 个点找出距离最近的两个点。朴素解法是两两比较O(n²) 复杂度当 n 到 10^5 级别时直接卡死。而这题的标准解法是分治能在 O(n log n) 时间内搞定很多第一次见到这个解法的人都会被“合并时只需要检查常数个点”这个结论震惊到。本文就围绕这道经典题从暴力思路到分治原理一步步拆开讲再给出一份可以直接抄作业的 C 实现最后分享几个我自己调试时踩过的坑适合学完基础分治、想啃经典例题的竞赛选手和算法爱好者。1. 题目到底在问什么1.1 题目描述与数据范围题目给出平面上 n 个点的坐标要求计算这 n 个点中距离最近的两个点之间的距离。坐标通常为实数或较大的整数输出一般要求保留 4 位小数。数据范围在不同平台上有差异常见的是 1 ≤ n ≤ 10^5坐标绝对值可以到 10^9。这个范围意味着 O(n²) 的暴力解法在 n 稍大时会超时必须寻找更高效的算法。n10^5 时两两组合约 5×10^9 对现代评测机每秒大约能跑 10^8 次简单运算暴力直接超时几个数量级。需要特别提醒的是题目所说“最近的一对”既可能要求输出距离值也可能要求输出是哪两个点。本文以输出距离值为例扩展部分再讲如何记录具体点对。1.2 先思考朴素解法暴力两层循环拿到题目先别急着写分治暴力解法的思路能帮我们校准后续所有优化。double ans 1e20; for (int i 0; i n; i) for (int j i 1; j n; j) ans min(ans, dist(p[i], p[j]));两层循环枚举所有点对计算欧几里得距离取最小值。这个写法的代码量极小5 分钟就能写完并保证正确适合用作对拍验证。数据规模不超过 5000 时暴力是完全可以接受的。但 n 一旦到 10^5暴力就不再可行。此时需要引入分治思想将问题不断拆成更小的子问题递归求解后合并结果。最近点对问题的经典解法就是分治算法它的核心在于“合并”这一步极其巧妙检查的点数被压缩到了一个常数。2. 分治思路拆解2.1 为什么选择分治而不是其他思路平面上求最近点对第一反应可能是排序后找相邻点。如果对所有点按 x 坐标排序分别计算相邻两点距离这样能保证找到最近点对吗不能。考虑两个点 x 坐标几乎相同但 y 坐标相差巨大它们之间可能隔着很多按 x 排序的“相邻”点但实际距离却很小反过来按 x 排序相邻的两个点也可能只是水平方向接近实际距离并不小。单靠一维排序无法刻画二维距离。更优的策略是分治把平面分成左右两半分别求左右两侧内部的最近距离再考虑跨越分割线的点对。这个“跨中点”的部分看起来还是 O(n²)但通过距离剪枝和几何性质可以压缩到线性扫描。分治将问题的规模逐步减半递归深度为 O(log n)合并阶段控制在 O(n)总复杂度 O(n log n)完美契合题目规模。2.2 分治的三个阶段划分、递归、合并分治解最近点对整体框架可以概括为三个阶段。划分阶段对点集按 x 坐标排序后取中间位置 mid (l r) / 2把点集拆成 left [l, mid] 和 right [mid1, r]。注意这里的分割线是一条竖直线x 坐标取中点而不是几何意义上的“均匀切”。分割线可以取点集中间点的 x 值也就是 x p[mid].x。递归阶段对左右两个子区间分别递归求最近距离得到 d_left 和 d_right令 d min(d_left, d_right)。这个 d 是当前已知的“安全上界”任何跨分割线的点对如果距离大于等于 d就不可能是最优解可以直接忽略。合并阶段这是整个算法最核心、也最容易被忽略的部分。分布在分割线两侧的点对左侧一个点、右侧一个点距离可能小于 d。理论上这样的点对数量可能非常多但我们可以利用一个几何结论来大幅压缩候选集如果一个点对的距离小于 d那么两个点的 x 坐标差必须小于 d也就是说两个点必须落在“距离分割线不超过 d”的窄带区域内我们把这个区域叫作候选带strip。2.3 合并时“候选带”的几何奥秘候选带内的点依然可能是 O(n) 个如果对这些点进行两两比较合并阶段最坏仍是 O(n²)整体复杂度退化为 O(n² log n)比暴力还差。但第二步剪枝让问题瞬间简化。将候选带内的点按 y 坐标排序后对于带内任意一个点 i只需要与后续的几个点比较距离。为什么因为当前全局最优值已经是 d我们只关心距离小于 d 的点对。如果把点 i 作为一个端点另一个端点 j 要满足距离小于 d那么 j 与 i 的 y 坐标差也必须小于 d。也就是说j 只能落在以 i 为中心、高为 2d、宽为 2d 的矩形区域里。这个矩形可以划分成若干个边长约为 d/2 的小格子。关键结论是如果格子划分合适每个小格子内最多只能有一个候选点否则这两个同格子内的点距离会小于 d这显然与“d 是当前最优距离”矛盾。把 2d × d 的矩形适当划分后可以证明矩形内最多还能容纳 6 个点因此每个点最多只需要与后续 7 个点进行比较。这正是合并阶段可以做到线性的原因。很多教科书直接把“比较 7 个点”当成结论但真正动手实现时你会发现写 7 还是写 6 都行只要保证常数足够更重要的是循环边界别越界。github 上很多实现直接用两层循环内层循环上限写 j tmp.size() (tmp[j].y - tmp[i].y) d这样也能保证复杂度近似线性因为一旦 y 坐标差超过 d 就跳出循环。3. 完整代码实现与解析3.1 坐标结构与排序要点先说结构体的定义。坐标可能是 int也遇到过浮点坐标的版本为了通用直接用 double 存坐标计算距离时也统一用 double。结构体struct Point { double x, y; };输入完成后先按 x 坐标排序。这一步很关键分治的“分割线”依赖这个顺序。如果有多个点 x 坐标相同排序顺序不影响正确性只需要保证 mid 左右两个子区间都非空。我自己习惯在主排序里同时把 y 排序也做了但后来发现不太对因为递归分治过程中每个子区间都需要按 y 序检查候选带而这个 y 序如果提前打好了每次直接筛选会省很多事。这里用到一个很实用的技巧开两个 Point 数组一个 P 存按 x 排序的点另一个 tmp 在合并阶段临时存放候选带内的点。P 在递归过程中一直用下标 l、r 分割tmp 则每次合并时填充并排序。vectorPoint p; Point tmp[MAXN];对于 n10^5递归深度约 17 层总空间复杂度 O(n)不需要担心内存。3.2 递归分治主函数核心递归函数参数是点在按 x 排序数组中的左右边界double solve(int l, int r) { if (l r) return INF; // 区间内没有点对 if (r - l 1 3) { // 点很少时直接暴力 double ans INF; for (int i l; i r; i) for (int j i 1; j r; j) ans min(ans, dist(p[i], p[j])); return ans; } int mid (l r) / 2; double midx p[mid].x; double d min(solve(l, mid), solve(mid 1, r)); // 合并阶段 int cnt 0; for (int i l; i r; i) if (fabs(p[i].x - midx) d) tmp[cnt] p[i]; sort(tmp, tmp cnt, cmp_y); for (int i 0; i cnt; i) { for (int j i 1; j cnt (tmp[j].y - tmp[i].y) d; j) { double dist_ij dist(tmp[i], tmp[j]); if (dist_ij d) d dist_ij; } } return d; }递归基的写法值得注意。当区间长度小于等于 3 时直接暴力枚举所有点对。这个阈值设成 3 还是 4 都无所谓设成 1 则返回 INF但这样递归基太少会增加大量函数调用开销。设成 3 能保证递归调用一定有非空子区间避免 l r 的情况同时暴力代价最多 3 次距离计算完全可接受。还有一个小细节mid (l r) / 2 要写在进入递归之前midx p[mid].x 也要在递归调用之前保存因为递归调用会修改 p 数组吗不会我们用的是两个数组p 自始至终保持按 x 排序递归调用不修改 p所以这里存不存 midx 其实无所谓。但为了代码逻辑清晰习惯上还是先存下来。3.3 合并检查与剪枝细节合并阶段分为三步我逐个展开说。第一步筛选候选带内的点。遍历整个 [l, r] 区间把 x 坐标与分割线 midx 的差值小于 d 的点挑出来。注意这里必须用绝对值 fabs如果不加绝对值会漏掉分割线左侧大量合法点。d 在递归返回后是当前左右两侧最近距离的最小值所以跨分割线的点对如果两个点的 x 距离超过 d它们的实际距离必然大于等于 d不可能更新答案直接跳过。第二步按 y 坐标排序。常见写法是sort(tmp, tmp cnt, cmp_y)cmp_y 是比较 y 坐标再比较 x 坐标避免相同 y 时的排序不稳定。bool cmp_y(const Point a, const Point b) { return a.y b.y; }第三步两层循环检查候选带内的点。外层遍历每个点 i内层从 i1 开始一直检查到两个点的 y 坐标差超过 d 为止。这个内层跳出条件至关重要它就是“最多比较 7 个点”的实现方式。如果不加这个跳出条件最坏情况仍是 O(cnt²)加了之后每个点最多与 y 坐标差小于 d 的其他几个点比较均摊下来线性。关于排序的复杂度要多说一句。每次合并都对 tmp 重新 sort总体复杂度是 O(n log²n)而不是教科书上最优的 O(n log n)。比赛里 10^5 规模跑 O(n log²n) 完全没问题因为 log²n 在 n10^5 时也就 289 左右常数也不大。如果想优化到严格的 O(n log n)需要在递归过程中维护按 y 排序的数组用归并代替 sort。这个优化笔试面试时可以提竞赛实战我建议直接 sort代码短、不易错性能也足够。4. 复杂度分析O(n log n) 是怎么来的4.1 递归主定理的直观推导设 T(n) 为处理 n 个点的总时间复杂度。分治过程把规模 n 的问题分成两个 n/2 的子问题合并阶段要遍历一次所有点放进候选带O(n)排序候选带O(n log n)再扫描候选带线性。于是递归式是T(n) 2T(n/2) O(n log n)用 Master Theorem 或者直接展开递归树看递归树的每一层总排序代价是 n log n 吗不对更仔细说是每一层的合并排序代价加起来是 O(n log n) 乘以层数。这种递归式的解是 T(n) O(n log² n)。当候选带排序换成归并优化后合并阶段变成线性递归式变为 T(n) 2T(n/2) O(n)解得 T(n) O(n log n)。我见过不少人纠结“到底标准复杂度是 O(n log n) 还是 O(n log² n)”。坦白说两种都能叫“分治法求最近点对”只是实现层面的差异。教科书上为了理论优雅会讲用归并维护 y 序让合并阶段线性化实际比赛里排序实现简单、通过率高我见过的选手大部分写的都是 O(n log² n) 版本在 n ≤ 10^5 时两者差距不大。但是有一点必须清楚如果 n 到了 10^6log² n 会明显拖慢速度到那时就应该上归并优化。4.2 常数级优化不只是理论玩具候选带扫描部分的“最多查 7 个点”是理论保证实际代码里我内层循环用的是 y 坐标差小于 d 作为条件而不是硬编码 7。原因有两个第一tmp 是按 y 排序的连续数组一旦 y 坐标差超过 d后面的点距离只会更大继续检查没有意义第二“最多 7 个”是矩形内最多有 6 个点加上自身是 7但这是最坏情况的理论上限实际点数往往更少用 y 差跳出条件可以让循环次数自适应。但从工程角度硬编码一个常数的写法我也见过且能通过只是边界处理稍麻烦。比较稳的写法是内层循环条件写(tmp[j].y - tmp[i].y) d这样既不会漏解也不会做无用功。另外计算距离时不必每次都用 sqrt。比较距离大小的时候可以比较平方和最后开一次根号。这样能把合并阶段的常数再砍一刀。实现时可以在 dist 函数里返回平方和最后在 main 里输出 sqrt(ans)。double dist(const Point a, const Point b) { double dx a.x - b.x; double dy a.y - b.y; return dx * dx dy * dy; }注意这样返回的是距离平方所以输出的地方要开根号。如果不小心把返回平方的函数用于逻辑判断但最后忘了开根答案会大很多调试时容易懵。我的习惯是写两个函数内部用平方比较最后输出开根命名分别为dis2和dis一眼就能看出区别。5. 常见问题与避坑实录5.1 递归边界与死循环分治最容易翻车的点之一是递归边界。假设 solve(l, r) 对应区间 [l, r]当 l r 时区间只有一个点不存在点对应返回 INF。如果 l r这说明区间非法同样返回 INF。我在初学时就踩过一个死循环的坑把递归基线写成if (r - l 1 3) break类似的思路退出条件是l r但左右区间划分用的是mid (l r) / 2当 l、r 距离很近时可能出现左区间是 [l, mid]右区间是 [mid1, r]其中一个区间为空却仍被递归调用的情况。比如 l0, r1 时如果阈值条件是3就直接暴力不会进入递归但如果把阈值调成 1就可能出现空区间递归。所以基线条件设成 3 不是随意的它能规避掉大部分空区间的坑。另一个类似的坑是用整数坐标但中位数计算时出现负数下标导致越界访问。建议在所有需要下标的地方先打印一遍 l、r、mid调试起来很快。5.2 候选带漏点、重复点与排序方向候选带筛选时最容易犯的错误是漏掉分割线上的点。如果分割线 x 坐标为 midx那么所有满足|p[i].x - midx| d的点都应该进入候选带注意用小于号而不是小于等于否则当 d 特别大时会把整条线上的点都包含进来增加无谓计算。这里用小于和小于等于都不影响正确性只是性能差异。重复点坐标完全相同是一个经典边界。两个重复点距离为 0算法会正确返回 0但要注意 INF 的取值。如果 INF 设小了比如 1e9而坐标范围是 10^9两点最大距离可能超过 1e9那么重复点距离 0 反而可能比 INF 大不会0 永远小于 INF。但如果所有点距离都大于 INF答案就可能出错。稳妥的做法是 INF 设为1e20或DBL_MAX的一半总之要比任何合法距离的上界大。按 y 排序的方向也需要注意。cmp_y 按 y 从小到大排那么内层循环判断tmp[j].y - tmp[i].y就是合理的。如果误写成从大到小这个差值是负的条件永远满足又退化成 O(cnt²)。5.3 浮点精度与输出格式浮点比较的精度问题是最后一个高频坑。坐标是整数时距离的平方可能超过 int 范围必须用 long long 或 double。计算平方差时我习惯全程 double最后输出保留 4 位小数用printf(%.4f\n, sqrt(ans))。有同学会问直接用double会不会有精度问题当坐标到 10^9平方后到 10^18double 的有效位数约 15-16 位理论上有误差风险。但比赛题目通常允许 1e-4 的相对误差double 完全够用。真正需要精度的竞赛题会提醒你用 long double 或提供整数坐标版这种情况下把坐标用 long long 存距离比较用平方和 long long 即可。我在处理洛谷 P1429 这类题时就发现 double 配合整数坐标输出.4f能过但心里清楚有个坑如果用cout输出浮点数且默认精度可能会被四舍五入到 6 位然后丢了精度所以务必写fixed setprecision(4)。经验上输入输出最好都用 scanf/printf因为数据量达到 10^5 时cin/cout 即使关同步也可能慢 10ms 级虽然不影响正确性但白给的性能不要白不要。6. 题目变种与扩展玩法6.1 要求输出最近的一对点是谁如果题目要求输出最近的两个点的编号或坐标朴素的分治返回值就不够用了。最简单的方法是引入全局变量ansA和ansB每次发现更小距离时记录这两个点的下标。递归基线暴力和合并扫描里凡是更新 d 的地方都要同步更新记录。这部分代码量很小但容易漏建议把所有更新 d 的地方统一封装成一个update(a, b)函数。void update(const Point a, const Point b) { double dd dis2(a, b); if (dd d) { d dd; ansA a; ansB b; } }注意输出时 ansA、ansB 可能是 NULL无解的情况比如 n1题目一般保证 n≥2 且答案存在但最好判断一下避免空指针访问。6.2 三维空间与曼哈顿距离的延伸最近点对的分治思想可以推广到三维空间只要把分割面从直线换成平面候选区从带状变成板状候选区域内的常数证明会复杂一些但框架不变。处理曼哈顿距离|x1-x2||y1-y2|也有技巧曼哈顿距离可以拆成四种情况用两个坐标组合的变换后求最值不一定要用分治用一个排序加前缀极值的思路就能在线性对数时间内解决。这些扩展我个人建议学有余力的同学去接触因为最近点对本身就是“分治思想能做很多看似二维难题”的经典例证。你掌握了它后面学三维凸包、KD-tree 等空间结构时会感觉顺很多。7. 写在最后一些竞赛实战心得最后分享几点我在实际做题过程中的体会这些不是算法书上会写的东西。第一写分治之前务必想清楚“合并时需要什么信息、排序发生在哪里”。很多同学看懂了原理一写就乱根源在于没有把递归函数的分工理清。建议先在纸上画出只有 5 个点的例子手推一遍合并过程再动笔写代码事半功倍。第二这道题特别适合用来练习对拍。暴力解法只有几行写一个随机数据生成器把暴力结果和分治结果对比能帮你确认边界处理是否完整。我当年调通这道题就是靠对拍发现了一个候选带漏掉等于 d 的点的 bug——虽然那个 bug 在数据量大时不一定触发但一旦触发就是 WA。第三如果是在比赛环境不要纠结 O(n log n) 和 O(n log² n) 的差距。先把排序版写法练熟能在 5 分钟内写完并通过样例比背诵一个归并优化但写不对的版本有价值得多。优化可以等理解了每一步之后再考虑。最近点对这道题背后的分治思想会反复出现在很多高级算法里比如平面最近邻查询、凸包问题的一些解法甚至计算几何的很多问题都离不开“分而治之再合并”的套路。把这道题吃透性价比非常高。