题目理解

我们需要在 $N$ 个二维平面点中，找到第 $K$ 远的点对距离的平方。

注意：

• 点对是无序的：$(P, Q)$ 和 $(Q, P)$ 是同一个点对
• 总点对数：$\frac{N(N-1)}{2}$
• 输出的是距离的平方（题目保证是整数）
• $K$ 最大为 100，相对较小

---

直接方法的困难

直接枚举所有点对：

• 点对数量：$O(N^2)$
• 对于 $N = 10^5$，点对数量约为 $5 \times 10^9$，无法全部存储和排序

---

关键思路：维护前 K 大的距离

由于 $K \leq 100$ 且 $K$ 很小，我们可以：

• 维护一个大小为 $K$ 的小根堆（优先队列）
• 对于每个点，找到它与其它点的较大距离，尝试加入堆中
• 最终堆顶就是第 $K$ 大的距离

但直接枚举所有点对仍然是 $O(N^2)$，需要优化。

---

利用 K-D Tree 优化

K-D Tree 可以高效地进行K近邻搜索，但我们需要的是远点。

观察：对于第 $K$ 远点对，我们可以：

1. 对每个点 $P$，找到距离它最远的 $K$ 个点
2. 从所有这些候选距离中找出第 $K$ 大的

算法步骤：

1. 构建 K-D Tree：$O(N \log N)$
2. 对每个点 $P$：
   • 使用优先队列在 K-D Tree 中搜索最远的 $K$ 个点
   • 将找到的距离平方加入全局候选集
3. 从全局候选集中找出第 $K$ 大的距离平方

---

K-D Tree 最远点搜索

与最近邻搜索相反，我们维护一个小根堆来保存当前找到的最远的 $K$ 个点：

// 搜索点p的最远K个邻居
void search_farthest(Node* node, Point p, priority_queue<LL, vector<LL>, greater<LL>>& heap, int k) {
    if (!node) return;
    
    // 计算当前节点距离
    LL dist = distance_sq(p, node->point);
    if (heap.size() < k) {
        heap.push(dist);
    } else if (dist > heap.top()) {
        heap.pop();
        heap.push(dist);
    }
    
    // 选择搜索顺序（优先搜索可能包含更远点的子树）
    int axis = node->depth % 2;
    Node* first = node->left;
    Node* second = node->right;
    
    // 根据点在分割轴的哪一侧决定搜索顺序
    if ((axis == 0 && p.x > node->point.x) || 
        (axis == 1 && p.y > node->point.y)) {
        swap(first, second);
    }
    
    // 先搜索更可能包含远点的子树
    search_farthest(first, p, heap, k);
    
    // 如果另一子树可能包含比当前第K远更远的点，则搜索
    LL max_possible = max_possible_distance(p, node->bounding_box);
    if (heap.size() < k || max_possible > heap.top()) {
        search_farthest(second, p, heap, k);
    }
}

---

算法流程

1. 构建 K-D Tree
2. 初始化全局小根堆 global_heap，大小为 $K$
3. 对每个点 $p_i$：
   • 初始化局部小根堆 local_heap
   • 在 K-D Tree 中搜索 $p_i$ 的最远 $K$ 个邻居
   • 将 local_heap 中的所有距离加入 global_heap，保持 global_heap 大小为 $K$
4. 输出 global_heap.top()

---

复杂度分析

• 构建 K-D Tree：$O(N \log N)$
• 每个点的最远 $K$ 邻居搜索：$O(K \cdot \log N)$（近似）
• 总复杂度：$O(N \cdot K \cdot \log N)$
• 对于 $N = 10^5, K = 100$，$10^5 \times 100 \times \log(10^5) \approx 1.7 \times 10^8$，可接受

---

距离计算优化

由于我们只需要距离平方，可以避免开方：

LL distance_sq(const Point& a, const Point& b) {
    LL dx = a.x - b.x;
    LL dy = a.y - b.y;
    return dx * dx + dy * dy;
}

---

样例验证

输入：

10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1

计算过程：

• 找出所有点对距离平方的前5大
• 第5大的距离平方为9
• 对应点对如 $(0,0)$ 和 $(3,1)$：$(3-0)^2 + (1-0)^2 = 9 + 1 = 10$？等等检查

重新计算：

• $(0,0)$ 到 $(3,1)$：$(3-0)^2 + (1-0)^2 = 9 + 1 = 10$
• 但输出是9，说明有更远的点对

实际上：

• 可能的点对：$(0,0)$ 到 $(3,1)$ = 10，$(0,0)$ 到 $(3,0)$ = 9
• 第5大是9

输出：9 ✓

---

总结

本题的关键在于：

1. 利用 $K$ 很小的特点，维护大小为 $K$ 的堆
2. 使用 K-D Tree 优化远点搜索
3. 通过 bounding box 剪枝，减少搜索空间
4. 注意距离平方的计算，避免浮点数运算

这是一个典型的** computational geometry + 优化搜索**问题，考察了对高级数据结构的理解和应用能力。