分治求最近点对的核心思路是先按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）。常见错误包括：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 误用
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 局部重排（仅限小段）。这个细节卡住的人，比算法理解不深的还多。
