分治法求最近点对的时间复杂度为o(n log n)，关键在于预处理排序、递归切分避免拷贝、合并时归并y有序子数组而非重复sort，且需注意浮点精度与边界处理。
为什么不能直接暴力枚举所有点对
当点数超过 10⁴，O(n²) 暴力会超时——尤其在竞赛或实时几何处理中。分治把时间压到 O(n log n)，但前提是点集能按 x 坐标排序，并支持高效合并“跨中线”的候选对。
核心步骤：排序 + 递归 + 中线带状扫描
算法不是黑盒，关键在三步协同：
- 预处理：用
std::sort按 x 坐标升序排点，避免每次递归重排 - 递归切分：用索引范围而非拷贝点数组（传
vector<pair>>&</pair>+l,r），否则O(n)拷贝毁掉复杂度 - 合并时只检查中线左右各
δ宽度内的点，且对这些点按 y 排序后，每个点最多只需比较后续 7 个点（理论保证）
容易崩的细节：y 方向排序不能每次都 sort
如果在合并阶段对带状区域点调用 std::sort，单次就 O(m log m)，整体退化为 O(n log² n)。正确做法是：递归返回时顺便按 y 排好序的子数组，合并时归并两个已排好序的 y 序列（O(m)）。用两个辅助 vector 或原地归并均可，但别现场 sort。
边界与精度：用 double 但慎用 ==
距离比较必须用 abs(d1 - d2) 而非 <code>d1 == d2；递归终止条件设为 r - l + 1 ，小规模直接暴力算，避免浮点误差放大；中线位置取 <code>(l + r) / 2 后对应点的 x 值，不是坐标平均值。
最易被忽略的是：归并 y 序列时，若用索引切片传递，必须确保左右子区间 y 序列都已有序——这要求递归函数返回「当前区间按 y 排好序的点引用」，而不是只返回最小距离。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
