C++如何使用分治算法寻找最近点对

分治求最近点对的核心思路是先按x排序，递归分割后在合并阶段仅检查中线附近y坐标差小于当前最小距离的常数个点（最多6~7个），避免退化为O(n²)。

分治求最近点对的核心思路是什么

分治法求二维平面上的最近点对，本质是把 std::vector<std::pair<double, double>> 按 x 坐标排序后递归切分，再合并时只检查跨中线、y 坐标落在当前最小距离内的候选点。关键不是“分”，而是“合”——合并阶段暴力检查的点数被严格限制在常数级（最多 6~7 个），否则退化成 O(n²)。

为什么必须先按 x 排序，还要维护 y 的有序结构

单纯每次合并前对子区间按 y 排序会导致 O(n log²n)；更优做法是：预排序一次 x，再用归并思想同步维护一个按 y 排序的副本（比如传入引用或索引数组）。常见错误是忽略这点，直接在 merge 阶段调用 std::sort，导致超时。

• 输入点集应提前用 std::sort(points.begin(), points.end()) 按 x 升序排好（std::pair 默认按 first 比较）
• 递归函数签名建议为 double closestUtil(std::vector<std::pair<double,double>>& points_y, int left, int right)，其中 points_y 是按 y 排序的索引或子视图，而非每次都重排
• 中线区域候选点提取时，用双指针或二分定位 y 范围，避免遍历全部点

合并阶段如何避免漏检和重复计算

中线带宽为 delta = std::min(left_min, right_min)，但候选点必须满足 abs(points[i].first - mid_x) < delta，且只对这些点按 y 排序后，逐个检查其后最多 6 个点（数学证明：单位正方形内最多放 4 个距离 ≥ δ 的点，扩展为带状区域后上限是 6 或 7）。常见错误包括：

• 误用 abs(points[i].second - points[j].second) < delta 作为外层循环条件（这会漏掉 y 差大但实际距离小的点）
• 内层循环写成 for (int k = j+1; k < points_y.size(); ++k)，没加 k - j < 7 限制
• 距离计算用 sqrt——完全没必要，比较平方距离即可，避免浮点误差和开销
• 没处理 n ≤ 3 的边界：此时直接暴力算所有点对距离

C++ 实现时容易踩的内存与精度坑

用 double 存坐标没问题，但距离比较必须用平方值；若点坐标范围极大（如 1e9），(x1-x2)*(x1-x2) 可能溢出，应转为 long long 或用 std::hypot（但慢）。另外，递归深度过深可能栈溢出，可改用迭代分治或手动扩栈（不推荐），更稳妥的是当区间大小

立即学习“C++免费学习笔记（深入）”；

• 初始化最小距离别用 INT_MAX——该类型无法存 double 平方距离，改用 DBL_MAX 或 1e18
• 中点 x 坐标取 points[mid].first，而非 (points[left].first + points[right].first)/2，后者在整数坐标下易错
• STL 容器传参尽量用引用，避免拷贝整个 vector；若用索引数组，注意 points_y 存的是原始点索引，不是点本身

实际写的时候，最麻烦的不是逻辑，是让中线候选点列表既按 y 有序、又不额外排序——要么预生成 y 排序的辅助数组并用归并更新，要么用 std::stable_sort 按 y 局部重排（仅限小段）。这个细节卡住的人，比算法理解不深的还多。