核心概述：在平面点集中以扫描线+有序集合在线维护候选点，求最近点对，时间 O(n log n)。
Description: Finds the closest pair of points. Time: O(n \log n) Status: stress-tested
展开阐述：
-
定义与背景
- 输入：n 个平面点，P=Point
（整数坐标）。 - 目标：找到欧氏距离最小的一对点 (a,b)。
- 应用：最近邻检索、聚类初始化、碰撞检测的粗筛等；与028-几何-凸包直径的“最远点对”互补。
- 输入：n 个平面点，P=Point
-
接口/数据结构（据实现）
- pair<P,P> closest(vector
v)
- 断言 sz(v) > 1，返回最近点对（点的副本）。
- pair<P,P> closest(vector
-
核心算法流程（扫描线 + set）
- 预处理：按 y 坐标排序点集 v（若相同 y，再按 x 排序保证稳定）。
- 维护：
- 有序集合 S：按照 x 坐标排序，保存“当前扫描线 y 范围内”的候选点。
- 指针 j：维护窗口下界，保持 S 中点的 y > v[i].y − d，其中 d 是当前最小距离的平方根（用距离平方 D 维护，比较时用 d = sqrt(D)）。
- 对每个点 p=v[i]：
- 移除：当 v[j].y ≤ p.y − d 时，从 S 删去 v[j]，j++。
- 区间查询：在 S 中二分寻找 x ∈ [p.x−d, p.x+d] 的候选点集合，仅与这些点计算距离平方并尝试更新全局最优。
- 插入：将 p 插入 S。
- 返回：记录的最近点对。
-
复杂度与边界条件
- 复杂度：排序 O(n log n)，每点最多插入/删除一次且区间查询均摊 O(log n + k)，整体 O(n log n)。
- 重合点：若存在相同坐标的点，最近距离为 0，应尽早短路。
- 去平方根：实现通常全程用距离平方比较，避免反复 sqrt，只有在窗口宽度 d 需要时取 sqrt(D)。
- 顺序一致性：若坐标为 ll，计算距离平方可能溢出 64 位，需使用内置 128 位或内联长整型扩展计算。
-
实现细节与常见坑
- 集合排序键：以 x 排序，查询时通过 lower_bound/upper_bound 做 x 的窗口过滤。
- 候选上界：理论上候选数量是常数期望（平面稀疏性），但实现上仍需遍历 [x−d,x+d]。
- 稳健性：若切换到 double 坐标，可直接用 double 距离平方（受精度影响），或以 long double 提高稳定性。
- 等距多解：实现通常返回遇到的任意一对最近点，如需按字典序稳定返回可在更新时增加比较规则。
-
变体与扩展
- 分治 O(n log n)：经典 divide-and-conquer 最近点对；实现复杂度更高但常数小。
- 高维推广：二维算法可推广到 kd-tree（见030-几何-kd树）进行最近邻查询，但语义不同（单源最近邻 vs 全局最近点对）。
- 动态数据流：可维护随机化或分桶结构做近似最近点对。
-
正确性要点与不变式
- S 中仅保留 y 与当前 p 相差小于 d 的点，保证不遗漏最优对。
- 仅检查 |x−p.x| ≤ d 的候选，来自最近点对的几何覆盖论证。
-
对比与取舍
- 与暴力 O(n^2) 相比，本算法在大 n 时显著加速。
- 与分治法相比，扫描线+集合实现相对简洁，常数可比肩或更优。