平面点对距离定义为min(|x1-x2|,|y1-y2|)，求第k小值的更优算法

你当前暴力枚举所有点对的实现仅适用于n<500的极小数据场景，当n规模达到数千以上时O(n²logn)的复杂度必然超时，下面是两种成熟的优化思路：

最优方案：二分答案 + 容斥计数 #

该方案综合实现难度和性能最优，可支持n到1e5的量级：

核心原理 #

将求第k小值的问题转化为判断问题：对于给定的距离d，统计有多少个点对的距离≤d。通过二分d的取值，不断调整边界最终收敛到第k小的距离。
计数部分利用容斥原理简化计算：
两点距离min(|x1-x2|,|y1-y2|) ≤d等价于x差≤d 或 y差≤d，根据容斥原理符合条件的点对总数为：
总计数 = x方向差≤d的点对数目 + y方向差≤d的点对数目 - 同时满足x差≤d且y差≤d的点对数目

实现步骤 #

1. 确定二分边界：左边界设为0，右边界取所有点x坐标的最大差值、y坐标最大差值的最大值
2. 每次取中间值mid作为阈值，按如下步骤计算符合条件的点对总数：
   • 将所有点按x坐标排序，滑动窗口统计所有x差≤mid的点对数目：对每个i，找到最大的j满足x[j]-x[i] ≤mid，累加j-i即为x方向总数
   • 同理将点按y坐标排序，滑动窗口统计y方向差≤mid的点对数目
   • 再次将点按x排序，滑动窗口维护x差≤mid的所有点的y坐标集合（用有序集合或离散化+树状数组维护），查询每个点y坐标前后d范围内的y值数量，累加得到同时满足x、y差≤mid的点对数目
   • 用x方向总数加y方向总数，减去重复统计的x、y同时满足的数目，得到最终的符合条件的点对总数
3. 如果总数≥k，说明第k小距离≤mid，缩小右边界；否则增大左边界，直到左右边界收敛即为答案

复杂度说明 #

每次计数的时间复杂度为O(nlogn)，二分次数最多为30次（坐标范围≤1e9的场景），整体复杂度为O(nlogn * log(max_dist))，空间复杂度为O(n)。

轻量优化方案：排序剪枝枚举 #

如果数据规模中等（n<2000），可以选择实现更简单的剪枝方案：

1. 将所有点按x坐标排序
2. 依然维护大小为k的最大堆，遍历每个点i时，仅和后面的点j比较，当x[j]-x[i]已经大于等于堆顶的最大距离时，直接break当前内层循环（因为后面的点x差更大，min距离必然大于堆顶，不可能进入堆）
3. 计算距离后如果小于堆顶再更新堆，随着堆顶数值不断变小，内层循环的break会越来越早，平均性能远高于暴力枚举，最坏情况复杂度为O(n²logk)。

现有代码问题修正 #

你贴出的C++代码中priority_queue pq;缺少模板参数，正确的最大堆声明应为priority_queue<int> pq;，另外可以加入提前终止逻辑：当堆顶元素已经为0时，直接返回0即可，无需继续枚举。

内容的提问来源于stack exchange，提问作者shreyak jain