实验二最近点对分治法：合并细节与C++/Python实现

实验二的分治法求解最近点对问题，是算法设计与分析这门课里最经典、也最能拉开差距的一个题目。它看起来只是"在一堆点里找距离最近的两个点"，但真正动手写就会发现问题并不在递归本身，而在合并那一步的细节：条带怎么筛、y 序怎么维持、递归出口取几个点、距离比较要不要开方。这些细节里任何一个写错，代码都能跑，但结果就是错的，而且错误还很难被发现，因为它只在特定数据上暴露。这篇内容我把整个实验从思路设计到代码落地再到排错复盘完整走一遍，代码给 C++ 和 Python 两个版本，都是可以直接编译运行、对拍验证的。适合正在做这个实验的同学，也适合把它当分治法入门案例来啃的人。

1. 实验二的真正考点：不是写出递归，而是想清楚合并

很多人第一次做这个实验，写完递归框架就以为结束了，结果卡在合并阶段整整一个下午。原因很简单：分治法的"分"和"治"都有固定套路，唯独"合"这一步，是每个问题独有的，也是最需要动脑子的地方。最近点对问题的合并阶段，本质上是在回答一个问题——最近的两个点，有可能一个在左半边、一个在右半边，我怎么在不枚举所有跨区点对的前提下把它们找出来。

1.1 最近点对问题的定义与暴力解的边界

先把问题说清楚。给定平面上 n 个点，找出其中距离最近的两个点，输出它们之间的距离。注意这里通常只要求输出最小距离这个数值，不要求输出具体是哪两个点，这一点在写代码时能省掉不少麻烦——不需要记录点的编号，只要维护一个全局最优值。

暴力解法的思路直白到不需要解释：两两枚举，维护最小距离。代码就是两层循环，时间复杂度 O(n²)。在 n 很小的时候，比如 n ≤ 1000，暴力解跑得比任何精巧算法都快，因为常数因子极小，而且没有递归开销。但一旦 n 上到 10⁵ 量级，两两枚举就是 5×10⁹ 次距离计算，哪怕每次计算只要几个纳秒，也是十几秒起步，直接超时。

这里有个经常被忽略的点：暴力法真正的瓶颈不是那两层循环的写法，而是距离计算里那个 sqrt。sqrt 是浮点运算里比较慢的一类指令，如果每次比较都开方，常数会明显变大。一个通用的小优化是全程比较平方距离，只在最后输出答案时开一次方。这个技巧在分治版本里同样适用，后面会专门讲。

所以实验二的定位其实很明确：n 的规模被刻意设得足够大，逼着你放弃暴力思路，去想一个 O(n log n) 的做法。而这个做法，就是分治。

1.2 分治法凭什么把 O(n²) 降到 O(n log n)

分治的思想一句话能说完：把点集按 x 坐标从中间劈成两半，分别递归求出左半边的最近距离 dL 和右半边的最近距离 dR，取 d = min(dL, dR)，然后处理跨界的点对。前两步的复杂度是标准的 2T(n/2)，如果合并阶段能做到 O(n)，整体就是 O(n log n)。

关键在于第三步。如果不做任何优化，跨界点对同样是 O(n²) 级别，分治就白做了。降复杂度的核心洞察是：跨界的最近点对，其距离一定小于 d。换句话说，如果一对点一个在左、一个在右，且它们之间的距离小于 d，那么这两个点的 x 坐标必然都落在中线的左右各 d 范围内，y 坐标的差值也必然小于 d。

这个观察把候选点从整个平面压缩到了一条宽度为 2d 的竖直条带里。条带宽度是 2d，不是 d，因为要同时覆盖中线左边 d 和右边 d 的范围。只有落在这条带子里的点，才有资格成为跨界最近点对的一员。落在外面的点，它到另一侧任意点的 x 方向距离就已经超过 d 了，不可能比当前最优更优。

条带筛完之后还没完。条带里的点如果仍然两两枚举，最坏情况下所有点都在条带上，退化成 O(n²)。所以还需要第二个观察：在条带内部，把点按 y 坐标排序，对每个点只需要往后看常数个点就能确定是否存在更优解。这个"常数"是 7，它的来源单独用一节讲清楚。

1.3 评分点拆解与最容易丢分的地方

从我见过的实验报告和代码来看，丢分基本集中在几个地方，而且这些地方有一个共同特征：代码能跑，样例能过，只有特定数据才能暴露。

第一类是递归出口处理不当。有的是 n 等于 2 还是 3 时进入暴力，判断写错导致数组越界；有的是完全没有终止条件之外的兜底，n=1 时去访问相邻元素。

第二类是划分方式错误。用中点坐标 (x[l] + x[r]) / 2 作为划分依据，而不是取排序后中位下标对应的坐标。这两者在点分布均匀时结果一样，但遇到大量 x 坐标相同的点，用坐标划分会把所有点分到同一侧，递归树退化成链，复杂度飙到 O(n²)，甚至栈溢出。

第三类是条带筛选的边界条件写错。比如只筛了中线左侧，忘了右侧；或者筛的时候用了 d 而不是 2d 的半宽；再或者 y 序扫描的剪枝条件是大于 d 而不是大于等于 d。

第四类是只对 x 排序，忘了 y 序。条带内部重新 sort 一遍也能过，但那样复杂度就是 O(n log²n)，虽然多数题目不会卡这个，但报告里的复杂度分析就会和代码对不上，属于自己给自己挖坑。

这四类问题合起来就是一句话：分治法的正确性藏在边界里，而边界是最不适合凭感觉写的地方。

2. 算法整体设计：拆、治、合三段式怎么落到代码上

把思路变成代码之前，得先把几个设计决策定下来。这些决策单独看都不复杂，但它们之间是相互牵制的，比如划分方式决定了递归参数怎么传，递归出口决定了暴力阈值取多少，条带扫描方式决定了要不要额外维护 y 序数组。先把这些理清，写代码就是填空题。

2.1 划分策略：为什么取中位下标而不是中点坐标

标准做法是先把所有点按 x 坐标排序，然后取下标 mid = (l + r) / 2 作为分界，左半部分是 [l, mid]，右半部分是 [mid+1, r]。分界线的 x 值就是 px[mid].x。

为什么不用坐标中点？假设所有点的 x 坐标都等于 5，比如一条竖直线上的点集。用坐标中点划分，midX 也等于 5，那么按"x < midX"和"x >= midX"来分，所有点都会落到右侧，左侧为空。递归下去规模只减 1，深度变成 n，复杂度直接崩。

用中位下标就没这个问题。无论坐标怎么重复，左半边和右半边的点数差不超过 1，递归树始终是平衡的，深度稳定在 log n。这是分治法里一个非常通用的经验：能按下标划分就别按值划分，除非你能保证值的分布足够均匀。

不过按中位下标划分会带来一个副作用：条带筛选的时候，怎么判断一个点属于左半边还是右半边？如果直接用坐标比较，遇到 x 相同的点又会出错。解决办法是给每个点绑定它在排序数组里的下标，用下标来判断归属。这个做法在后面代码里会看到。

2.2 递归出口的三种写法与取舍

递归出口有三种常见写法，各有取舍。

第一种是 n ≤ 3 时直接暴力。三个点最多 3 对，暴力计算开销极小，而且能省掉两层递归调用。这是最常用的写法，代码最短。

第二种是 n ≤ 2 时直接返回距离。这样递归会多走一层，但因为点数少，影响可以忽略。好处是逻辑更"干净"，每一层递归处理的规模都不小于 2。

第三种是 n 小于某个更大的阈值，比如 16 或 32 时暴力。这个写法在多核或者大规模数据下反而更快，因为小规模下递归调用的函数开销已经超过了暴力枚举的收益。实际工程代码里常见这种"混合策略"，算法竞赛里也比较常见。

对于课程实验，我建议用第一种或者第三种。用第一种的时候要注意 n 必须至少是 2 才能进入暴力计算，否则内层循环会出错，所以在调用入口处要先判断总点数。用第三种的时候要注意阈值别设得太大，32 是个比较稳妥的上限。

还有一种更保险的写法：递归前判断 r - l + 1 <= 3，同时在整个函数的最开头加一句 if (l >= r) return INF;，用无穷大表示不存在点对。这样即使边界条件写漏了也有兜底，不会崩。

2.3 合并阶段：条带筛选与 y 序扫描的配合

合并阶段分两步，必须先筛条带、再按 y 序扫描，顺序不能反。

筛条带的判据是 |p.x - midX| < d。用严格小于还是小于等于，理论上都可以，因为等于 d 的点对不可能比 d 更优。但如果 d 已经是当前最优，把边界点放进来也不会算错，只是多做几次无用比较。我习惯用小于等于，剪枝逻辑上更保守一点，不容易因为浮点误差漏掉点。

筛完之后，把条带内的点按 y 坐标升序排列，然后对每个点 i，只检查后面那些 y 差值小于 d 的点 j。这个内层循环一旦遇到 y 差值大于等于 d 就 break，因为后面的点 y 更大，差值只会继续扩大。

这里有一个必须注意的细节：条带内的点是按 y 排序的，但它们的 y 值可能有重复。遇到 y 相同的情况，采用什么稳定的排序、索引怎么处理，都不影响结果正确性，因为距离比较本身是对称的。但如果用 sort 而不是稳定排序，又同时依赖下标做其他判断，就可能出问题。稳妥做法是所有判断都基于坐标值，不依赖排序后的相对顺序。

还有一个容易被忽略的性能点：条带数组每次递归都要重新构造。如果每层递归都 new 一个 vector，分配开销会累积。用 reserve 预留容量，或者干脆用全局的临时数组加长度标记，能省掉不少 malloc 时间。在小数据上感觉不出来，在大数据上能差出可观的百分比。

3. 那个绕不开的 7 个点：合并常数怎么来的

每个讲分治最近点对的资料都会提到"每个点最多检查 7 个点"，但很多人只是背下来，并不清楚为什么是 7，更不知道这个数字在实现里意味着什么。这个证明本身不难，理解了之后，写剪枝条件时会更有底气，实验报告里的正确性论证部分也能写得扎实。

3.1 用鸽巢原理把 7 讲明白

考虑合并阶段那条宽度为 2d、高度不限的竖直条带。我们现在关注条带里任意一个点 p，并把目光限制在 p 上方 y 差值小于 d 的那部分区域。这个区域的形状是：宽 2d、高 d 的矩形。

把 p 所属的那一侧看成半宽 d 的矩形，也就是宽 d、高 d 的正方形。这个正方形正好在半边之内。现在用鸽巢原理：把左半边这个 d × d 的正方形切成 4 个边长 d/2 的小正方形。如果两个点落在同一个小正方形里，它们之间的距离最大是多少？是小正方形的对角线，长度是 (d/2) × √2 ≈ 0.707d，严格小于 d。

但这里出现了一个矛盾：d 是左半边的最小点对距离，左半边内任意两个点的距离都不可能小于 d。所以每个 d/2 × d/2 的小正方形里，最多只能有一个点。左半边的 d × d 正方形里最多 4 个点，右半边同理最多 4 个点。两边合起来，在 p 上方这个 d 高度的矩形区域内，最多有 8 个点，其中 p 自己占一个，所以 p 最多只需要和其他 7 个点比较。

这就是"7"的来源。有些资料写 6，是因为把 p 自己所在的那个格子也排除之后，严格需要检查的数量在更精细的划分下可以压到 6，但在代码实现里，7 已经足够，因为剪枝条件本身已经能挡掉绝大多数无意义的比较。

3.2 常数背后的实际意义

搞清楚 7 的来历，最大的价值不是省下那几次比较，而是让你明白这个剪枝为什么是对的，从而在写代码时不会写出"看起来差不多但实际漏解"的条件。

比如一个常见的错误写法是：内层循环只检查紧跟其后的固定 7 个点，第 8 个点直接跳过。这个写法在大多数数据上能过，但理论上是有风险的，因为"7"这个结论依赖于 d 是当前最优且分治结构完整的前提。真正安全的写法是用 y 差值做剪枝——只要 y 差值小于 d 就继续检查，不设固定次数上限。这样既不漏解，实际运行中也会因为剪枝条件自动把比较次数控制在常数级。

另一个容易混淆的点是：7 这个结论针对的是"每半边最多几个点"，而不是"每个点最多检查几个点"。严格推导下来，每个点需要检查的候选数量是常数 7，但实际代码里由于先按 y 排好序、再按 y 差剪枝，比较次数往往远小于 7，因为大部分点的 y 差值一开始就超过 d 了。

3.3 递推式与主定理的完整推导

把复杂度算清楚，是实验报告里必写的部分，也是很多人写得含糊的地方。

设 T(n) 是处理 n 个点所需的时间。递归分成两个规模为 n/2 的子问题，加上合并阶段的线性工作，递推式是 T(n) = 2T(n/2) + O(n)。

为什么是 O(n)？拆开看：筛条带需要遍历当前区间的所有点，O(n)。条带按 y 排序，如果每次重新排序，是 O(k log k)，其中 k 是条带内点数，最坏等于 n，整体就退化成 O(n log n) 的合并，总复杂度变成 O(n log² n)。如果提前维护好 y 序，合并时只做遍历和归并，就真的是 O(n)。

主定理第二种情况：a = 2，b = 2，f(n) = O(n)，而 log_b(a) = log₂2 = 1，也就是 f(n) = Θ(n^1)，属于 f(n) = Θ(n^{log_b a}) 的情形，结论是 T(n) = Θ(n log n)。换成递归树的说法更直观：每一层的合并总代价都是 O(n)，一共有 log n 层，乘起来就是 O(n log n)。

再加上最开始那次按 x 排序的预处理，也是 O(n log n)，所以整体复杂度是 O(n log n)。如果合并阶段用了排序而不是归并，复杂度就是 O(n log² n)，虽然实践中可能还是能过题，但报告里的推导就对不上了，属于典型的"代码和结论打架"。

4. 可跑通的实现：C++ 与 Python 双版本

理论讲完，落到代码。下面两个版本都是按 O(n log n) 写的，核心是提前维护 y 序，避免递归里重复排序。C++ 版本适合交实验，Python 版本适合理解逻辑，但要注意 Python 在大数据下常数较大。

4.1 数据结构设计与预排序

点用结构体或元组表示，两个 double 或 int。首先要做的预处理有两件事：把点按 x 升序排序，得到一个数组 px；再构造一个下标数组，按下标对应的 y 坐标升序排列，得到 yIdx。

为什么用下标数组而不是直接复制点？因为在递归划分时，需要同时保证左右两侧的顺序稳定，用下标可以直接判断归属，而且复制开销更小。yIdx 在递归内部会被拆成左右两部分，但这两部分本身就保持 y 序，不需要重新排序，这就是省掉一次排序的关键。

预排序之后，递归函数需要四个参数：当前处理的左边界 l、右边界 r、按 x 排序的数组 px、以及当前区间内按 y 排序的下标列表 yIdx。注意 yIdx 只包含 [l, r] 范围内的下标，且按对应点的 y 排序。

4.2 C++ 完整实现（O(n log n) 归并版）

下面是完整可编译的版本。核心细节都在注释里。

#include <bits/stdc++.h> using namespace std; struct Point { double x, y; }; double dist2(const Point& a, const Point& b) { double dx = a.x - b.x; double dy = a.y - b.y; return dx * dx + dy * dy; } bool cmpx(const Point& a, const Point& b) { return a.x < b.x; } // 暴力求解，返回平方距离的最小值 double bruteForce(const vector<Point>& px, int l, int r) { double best = DBL_MAX; for (int i = l; i <= r; ++i) for (int j = i + 1; j <= r; ++j) best = min(best, dist2(px[i], px[j])); return best; } // px 按 x 升序，yIdx 是 [l, r] 内点按 y 升序排列的下标 double solve(const vector<Point>& px, const vector<int>& yIdx, int l, int r) { int n = r - l + 1; if (n <= 3) return bruteForce(px, l, r); int mid = (l + r) >> 1; double midX = px[mid].x; // 按排序下标划分 y 序，左半边下标 <= mid vector<int> yl, yr; yl.reserve(mid - l + 1); yr.reserve(r - mid); for (int id : yIdx) { if (id <= mid) yl.push_back(id); else yr.push_back(id); } double dl = solve(px, yl, l, mid); double dr = solve(px, yr, mid + 1, r); double d2 = min(dl, dr); double d = sqrt(d2); // 筛条带 vector<int> strip; strip.reserve(n); for (int id : yIdx) { if (fabs(px[id].x - midX) <= d) strip.push_back(id); } // 按 y 序扫描，只检查 y 差小于 d 的点 for (size_t i = 0; i < strip.size(); ++i) { for (size_t j = i + 1; j < strip.size(); ++j) { double dy = px[strip[j]].y - px[strip[i]].y; if (dy >= d) break; d2 = min(d2, dist2(px[strip[i]], px[strip[j]])); d = sqrt(d2); } } return d2; } double closestPair(vector<Point> pts) { sort(pts.begin(), pts.end(), cmpx); int n = pts.size(); vector<int> yIdx(n); iota(yIdx.begin(), yIdx.end(), 0); sort(yIdx.begin(), yIdx.end(), [&](int a, int b) { return pts[a].y < pts[b].y; }); return sqrt(solve(pts, yIdx, 0, n - 1)); }

这段代码里有几个地方值得单独说明。距离全程用平方值比较，只有在更新 d 的时候才开一次方，这样既避免了频繁 sqrt，又保证了条带剪枝用的 d 是真实的距离值。yIdx 在递归中被拆成 yl 和 yr 两个新数组，它们天然保持 y 升序，因为拆分只是按条件过滤，没有改变相对顺序。

关于dy >= d这个 break 条件：因为 strip 已经按 y 升序，一旦某个点的 y 差达到 d，后面的点 y 只会更大，差值只会更大，所以可以直接跳出。这是 O(n) 合并的关键。

还有个细节是 d 在循环中会缩小，所以剪枝条件也在动态收紧，这样能进一步减少比较次数。这是个小优化，但在点比较密集的数据上效果明显。

4.3 Python 完整实现与递归深度处理

Python 版本逻辑完全一致，但有几个坑要提前说。第一是递归深度，默认 1000 层，n 较大时会爆栈，必须手动调高。第二是切片和列表推导会产生大量临时对象，n 超过 10⁵ 之后可能会很慢，需要用 sys.stdin 读入并且尽量在函数内复用局部变量。

import sys, math def dist2(a, b): dx = a[0] - b[0] dy = a[1] - b[1] return dx * dx + dy * dy def brute(px, l, r): best = float('inf') for i in range(l, r + 1): for j in range(i + 1, r + 1): d = dist2(px[i], px[j]) if d < best: best = d return best def solve(px, yidx, l, r): n = r - l + 1 if n <= 3: return brute(px, l, r) mid = (l + r) // 2 midx = px[mid][0] yl = [i for i in yidx if i <= mid] yr = [i for i in yidx if i > mid] d2 = min(solve(px, yl, l, mid), solve(px, yr, mid + 1, r)) d = math.sqrt(d2) strip = [i for i in yidx if abs(px[i][0] - midx) <= d] m = len(strip) for i in range(m): for j in range(i + 1, m): dy = px[strip[j]][1] - px[strip[i]][1] if dy >= d: break nd = dist2(px[strip[i]], px[strip[j]]) if nd < d2: d2 = nd d = math.sqrt(d2) return d2 def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) pts = [] idx = 1 for _ in range(n): pts.append((float(data[idx]), float(data[idx + 1]))) idx += 2 pts.sort(key=lambda p: p[0]) yidx = sorted(range(n), key=lambda i: pts[i][1]) print(f"{math.sqrt(solve(pts, yidx, 0, n - 1)):.6f}") if __name__ == "__main__": sys.setrecursionlimit(1 << 20) main()

Python 里最容易出问题的是sys.setrecursionlimit的调用位置。如果写在 main 里面，而 main 之前已经发生了递归调用，就来不及了。稳妥做法是在文件顶部调用，或者放在 ifname块的第一行。另外 n 特别大的时候，递归层数大约是 log₂n，10⁵ 个点也就 17 层左右，其实远达不到默认上限。真正会爆栈的情况反而是划分不均导致的退化，比如按坐标划分遇到大量重复 x 值——这也是前面强调用下标划分的原因之一。

4.4 距离比较中的开方优化

sqrt 的开销在浮点运算里属于中等偏上，如果每次点对比较都开方，几百万次下来会明显拖慢速度。优化的做法是全程维护平方距离 d2，只有在需要和坐标差值比较的时候才临时取一次 d = sqrt(d2)。

要注意的是，d2 本身不能直接用来做条带筛选，因为条带筛选的比较对象是 x 方向的差值，量纲是长度而不是长度平方。所以每次 d2 更新后，如果要继续用于条带判断或者 y 差剪枝，就得重新算一次 sqrt。这个重算次数很少，因为 d2 只在真正找到更优解时才更新，大多数比较都只是更新 d2 而不影响后续剪枝。

一个更极端的优化是全程用 d2 做片内比较，只在最后输出时开方，条带和 y 差剪枝用上一次的 d 值。这种做法在数据规模极大时能再快一些，但边界处理会变复杂，容易因为 d 没有及时更新而漏掉某些点。课程实验里不建议这么写，收益不明显，风险倒是实打实的。

还有一个和浮点相关的小细节：用 fabs 比较 x 差值的时候，如果 d 是 0（有重合点），那么所有点都会进入条带，条带扫描退化成 O(k²)。虽然此时答案已经是 0，可以提前返回，但代码里加一个 d == 0 的提前退出判断会更稳妥。我在实测里遇到过一组全是同一个坐标的测试数据，不加这个判断的话运行时间直接从毫秒级涨到秒级。

5. 正确性怎么验证：对照暴力与边界数据

写完代码不等于做完了实验。真正决定得分的，是有没有系统地验证过正确性。最省事也最有效的方法是对拍：用小规模随机数据同时跑暴力法和分治法，比较输出是否一致。这一步能抓出绝大多数逻辑错误。

5.1 随机数据对拍脚本

对拍的思路很简单：写一个暴力函数作为标准答案，反复生成随机点集，比较两个结果。为了能抓到浮点误差，比较时用一个很小的容差，比如 1e-6。下面是一个 C++ 对拍模板。

#include <bits/stdc++.h> using namespace std; // 暴力标准答案 double brute(std::vector<pair<double,double>> pts) { double best = 1e18; for (size_t i = 0; i < pts.size(); ++i) for (size_t j = i + 1; j < pts.size(); ++j) { double dx = pts[i].first - pts[j].first; double dy = pts[i].second - pts[j].second; best = std::min(best, std::sqrt(dx*dx + dy*dy)); } return best; } int main() { std::mt19937 rng(12345); std::uniform_real_distribution<double> coord(-1000.0, 1000.0); std::uniform_int_distribution<int> cnt(2, 60); for (int t = 0; t < 2000; ++t) { int n = cnt(rng); std::vector<pair<double,double>> pts; for (int i = 0; i < n; ++i) pts.push_back({coord(rng), coord(rng)}); double expect = brute(pts); double got = closestPair(pts); // 换成你自己的分治实现 if (std::fabs(expect - got) > 1e-6) { std::cout << "Mismatch at test " << t << "\n"; std::cout << "expect=" << expect << " got=" << got << "\n"; for (auto& p : pts) std::cout << p.first << " " << p.second << "\n"; return 1; } } std::cout << "All tests passed\n"; return 0; }

对拍的时候把数据规模控制在 60 以内，这样暴力法跑得飞快，2000 组测试几秒钟就能跑完。如果 2000 组都过了，那基本可以认为逻辑是对的。这里有个经验：不要只跑随机数据，随机数据往往分布均匀，反而掩盖边界问题。生成数据的时候可以故意让坐标取一些重复值，比如把坐标四舍五入到整数，或者只用 {0, 1, 2} 这几个值，这样更容易触发重复 x、重复 y 的情况。

5.2 必须覆盖的边界与退化数据

对拍过了之后，还要单独测几组手工构造的数据。这些数据不是用来验证算法主流程的，而是用来验证边界条件的。

第一组是 n = 2 的最小规模。答案就是这两点的距离。

第二组是所有点在同一条竖直线上，x 全部相同。这组数据专门用来检验划分方式。如果用坐标中点划分，会退化得很惨；用下标划分则完全正常，答案就是相邻两点 y 差值的最小值。

第三组是所有点在同一条水平线上，y 全部相同。这组数据和上一组对称。要注意 y 相同意味着条带里的点 y 差值全是 0，剪枝条件dy >= d在 d 不为 0 时不会触发，所有候选点都会被检查。如果 d 恰好是 0，就要靠提前返回判断了。所以这组数据能同时检验剪枝逻辑和零距离处理。

第四组是有重合点的情况。如果存在两个完全相同坐标的点，答案就是 0。代码里要在 d 变成 0 时尽早返回，否则条带会包含所有点，性能骤降。

第五组是圆环分布。把点全部放在一个圆上，最近距离出现在相邻点之间，但分界可能切在任意位置，用来检验跨界的合并逻辑是否真的在起作用。

第六组是两根密集簇，两簇之间距离很大。这种数据下，条带会非常窄，主要考察剪枝效率。

第七组是全随机的大数据，n 取 1e5 或 2e5，用来测性能。这组不进对拍，只看运行时间。

5.3 精度与输出格式

输出格式是很容易被扣分的细节。多数题目要求保留 2 位小数，有的要求 6 位。用 printf 的%.2f或者 C++ 的fixed << setprecision(2)都行。Python 用 f-string 的:.6f。

这里有个坑：如果题目要求输出保留两位小数，而真实答案计算出来是 1.005，浮点表示可能是 1.00499999，四舍五入后输出 1.00 而不是 1.01。这是浮点精度的固有问题，通常评测数据会避开这类边界值，但如果你自己造数据测试，看到这种"差一分"的情况不用慌，先确认是不是精度问题。

还有一个更隐蔽的精度问题：如果全程用 float 而不是 double，在坐标范围较大的时候，平方和会损失有效数字，导致比较结果出错。平面点对问题的坐标范围通常给到 1e4 或 1e9，float 只有 7 位有效数字，根本不够用。所以一律用 double，不要图省事用 float。

6. 踩坑实录：我见过的高频错误排查表

前面几节讲的是"应该怎么写"，这一节讲"写错了怎么查"。这些错误我自己踩过，也在帮别人看代码时反复见到。它们的共同点是：编译能过，样例能过，只有在特定输入下才暴露。所以排查的核心思路是构造能触发问题的数据，而不是盯着代码看。

6.1 递归死循环与索引越界

递归死循环通常发生在两种情况下。一种是没有正确的终止条件，比如判断写成n <= 0而实际最小规模是 1，或者用坐标判断终止导致某个子问题规模没有缩小。另一种是划分子问题时边界写错，比如左半边写成[l, mid]，右半边写成[mid, r]，mid 被重复计算，规模不收敛。

排查方法很直接：在递归函数开头打印 l 和 r，再加一个深度计数，如果深度超过 2 * log₂n 就说明出问题了。或者更简单，在函数里加一句断言assert(r - l + 1 >= 1)，配合一个全局的调用次数上限，越界会立刻暴露。

索引越界最常见的地方是暴力出口。如果出口判断写成n <= 3，但实际处理的时候用px[j]访问，而 j 的取值范围没算对，就会越界。可以先在出口里打印一遍参数确认。另外，Python 里列表越界会直接抛异常，C++ 里则是未定义行为，可能读到垃圾值继续算，症状更隐蔽。

6.2 条带筛选写错的几种花样

条带筛选写错，症状是结果偏大——因为漏掉了某些本来更优的跨区点对。具体表现有几种。

一种是只筛了左侧没筛右侧，或者反过来。判据fabs(px[id].x - midX) <= d本身是对称的，只要条件写对就不会漏。但如果写成px[id].x - midX <= d而不加绝对值，就等于只筛了左侧，右侧的所有点全部漏掉。

另一种是筛选宽度用错。有人把宽度记成 d，于是写成fabs(...) <= d / 2，这样条带太窄，边界附近的点对被漏掉。正确宽度是左右各 d，所以判据里的阈值就是 d。

还有一种是剪枝条件写反。把dy >= d写成dy <= d，前者的意思是"超过 d 就跳出"，后者的意思是"只要小于等于 d 就跳出"，完全相反，会导致内层循环几乎不执行，结果严重偏大。

排查这类错误有个诀窍：把所有点的规模缩到 10 以内，然后随机生成几千组数据，只要有一组结果不一致，就把那组数据打出来单独调试。这种小规模不一致一定能被随机对拍抓到。

6.3 只按 x 排序埋下的隐性错误

只按 x 排序、条带里重新 sort y 的写法，本身不是错误，只是复杂度退化成 O(n log² n)。但如果在这个过程中用了全局的 y 数组或者共享状态，就可能引入真正的错误。

比如有一种写法是维护一个全局的 y 序数组，递归时通过临时交换元素来维持顺序。这种写法在 C++ 里比较常见，效率高，但很容易写错。一旦交换的顺序和递归的划分不一致，就会导致条带里的点不是按 y 排序的，剪枝条件dy >= d直接失效，结果就错了。

如果不想折腾归并，最稳的做法就是每层递归重新筛一遍条带、重新排序。这个版本的代码虽然复杂度高一点，但正确性最容易保证。等确认正确之后，再考虑优化成归并版。这是我一直推荐的做法：先写对，再写快。

6.4 常见问题速查表

下面这张表把高频问题和排查方向整理在一起，卡住的时候可以直接对照。

这张表里出现频率最高的是前两项。尤其是"结果偏大"这一类，九成以上是条带筛选或者剪枝条件的问题。Debug 的时候，最简单的办法是在合并阶段把条带里的点数打印出来，正常情况下它应该远小于当前区间总点数。如果条带点数等于甚至超过区间点数，说明筛选条件没起作用。

还有一个经验：如果对拍一直过不去，先别改逻辑，把 d 的中间值打印出来。看看每层递归返回的 d 是不是单调不增的。如果不增反增，说明某个子问题返回了错误的大值，问题就在那一层。

7. 实验报告加分项与性能实测

代码写完、对拍通过，实验只完成了一半。实验报告里能体现思考深度的部分，才是拉开分数的地方。这部分我按实际写报告的经验，说几个容易被忽略但确实能加分的点。

7.1 报告结构怎么组织

一份完整的报告至少要包含这几块：问题描述、算法设计思路、正确性论证、复杂度分析、实现细节、测试结果、结论。

问题描述部分不用写太多，把输入输出格式说清楚就够了。算法设计思路是重点，要把"为什么分治""为什么只筛条带""为什么每个点只检查常数个"这三层逻辑讲明白。正确性论证部分，很多人只写一句"由归纳法可证"，这太单薄。至少要说明归纳的基本情况（n ≤ 3 时暴力正确）和归纳步骤（假设子问题正确，证明合并后仍然正确）。

复杂度分析要写清递推式、主定理的适用情形、以及预处理排序的代价。如果实现里用了额外的归并，要说明为什么合并是 O(n) 而不是 O(n log n)。这部分写清楚了，报告的专业度立刻上一个档次。

测试结果部分建议用表格呈现，至少包含对拍结果（多少组、是否全部通过）和性能数据（不同 n 下的运行时间）。表格比大段文字有说服力得多。

7.2 性能实测与暴力法对比

我本机跑过的一组参考数据大致是这样：n = 1000 时，暴力法和分治法都在毫秒级，分治反而略慢，因为递归和内存分配的开销还没被摊薄。n = 10000 时，暴力法大约是几百毫秒量级，分治法还在 10 毫秒以内。n = 100000 时，暴力法已经需要数十秒，分治法依旧在几十毫秒到一百毫秒之间。具体的绝对值取决于机器和实现，但这个变化趋势是稳定的。

这个对比本身就很有价值：它说明分治法的优势不在于小数据，而在于数据规模上去之后增长率完全不同。报告里如果只放一张"分治法更快"的结论，说服力有限；把不同 n 下的实测时间列成表，再画一条随 n 变化的曲线，结论就扎实了。

测性能的时候有几个注意点。第一，要关掉编译器的优化之外的所有调试输出，printf 在循环里会拖慢几十倍。第二，至少跑三次取平均，单次结果波动可能很大。第三，输入数据的读取时间要单独考虑，如果用 cin 不加同步关闭，读 10 万个点可能就要花掉跟算法本身相当的时间。加一句ios::sync_with_stdio(false); cin.tie(nullptr);是基本操作。

7.3 可以继续往下做的扩展

这个实验的框架其实可以往几个方向延伸，写进报告的"扩展思考"里很出彩。

第一个方向是三维最近点对。把平面问题推广到空间，分治的框架不变，但合并阶段的常数会变大，条带的形状从矩形变成无限高的长方体，剪枝的几何论证也要重新做。这个扩展能检验你是否真的理解了合并阶段为什么只要常数次比较。

第二个方向是带权最近点对，每个点有一个权重，距离定义为坐标距离乘以权重系数。这种情况下暴力部分照旧，但分治的正确性需要重新论证，因为"左半边最优"和"右半边最优"的组合不一定还是最优。

第三个方向是动态维护最近点对，点会不断插入和删除，要求实时查询最近距离。这就从静态分治变成了数据结构问题，通常用网格或者平衡树来做，思路完全不同。

第四个方向是并行化。分治的两个子问题天然独立，可以并行执行，合并阶段串行。用 OpenMP 加一行 pragma 就能试出加速比，报告里给个实测数据很有意思。要注意的是并行开销在小数据上会拖后腿，得测出临界规模。

这几个扩展不用全做，挑一个深入地做，把思路和实测结果写清楚，比泛泛地列四个方向要强得多。

最后分享一个我在写这类几何分治题时养成的小习惯：先写一个绝对正确但很慢的暴力版本，把它当成"标准答案生成器"，任何时候改了主算法，都先拿它对拍几百组随机数据，通过了再去看性能。这个流程看着笨，但能省掉大量"改了一行代码结果错了却不知道错在哪"的时间。分治法的合并阶段尤其如此，因为它的正确性依赖于好几个条件同时成立，肉眼检查几乎不可能可靠。对拍这种机械但有效的验证方式，才是这类题真正的护城河。