题解：平面最近点对与最远点对

算法思路

本题需要同时求解平面点集中最近点对和最远点对的距离，采用 KD-Tree 算法高效解决。

1. KD-Tree 构建

• 按深度轮流选择分割轴（x轴和y轴交替）
• 使用 nth_element 快速选择中位数点作为分割点
• 递归构建左右子树，维护每个节点的包围盒

2. 最近邻搜索

对于每个点查询其最近邻：

• 计算当前节点距离，更新最小值
• 使用最小可能距离进行剪枝：$$d_{min} = \sum_{i=0}^1 \begin{cases} (mi_i - p_i)^2 & \text{if } p_i < mi_i \\ (p_i - mx_i)^2 & \text{if } p_i > mx_i \\ 0 & \text{otherwise} \end{cases}$$
• 优先搜索更可能有近邻的子树

3. 最远邻搜索

对于每个点查询其最远邻：

• 计算当前节点距离，更新最大值
• 使用最大可能距离进行剪枝：$$d_{max} = \sum_{i=0}^1 \max((p_i - mi_i)^2, (mx_i - p_i)^2) $$
• 优先搜索更可能有远邻的子树

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
const int N = 1e6 + 3;
ll n, cur;
db ans_min_sq, ans_max_sq;  // 存储平方距离

struct Point {
    db x[2];
} p[N];

struct Node {
    db mx[2], mi[2];  // 包围盒边界
    int ls, rs;       // 左右子树
    Point tp;         // 当前节点代表的点
} tr[N];

// 按维度比较
bool Cmp(const Point& a, const Point& b, int kd) {
    return a.x[kd] < b.x[kd];
}

// 更新节点包围盒
void update(int k) {
    int l = tr[k].ls, r = tr[k].rs;
    Node& o = tr[k];
    o.mi[0] = o.mx[0] = o.tp.x[0];
    o.mi[1] = o.mx[1] = o.tp.x[1];
    if (l) {
        o.mi[0] = min(o.mi[0], tr[l].mi[0]);
        o.mx[0] = max(o.mx[0], tr[l].mx[0]);
        o.mi[1] = min(o.mi[1], tr[l].mi[1]);
        o.mx[1] = max(o.mx[1], tr[l].mx[1]);
    }
    if (r) {
        o.mi[0] = min(o.mi[0], tr[r].mi[0]);
        o.mx[0] = max(o.mx[0], tr[r].mx[0]);
        o.mi[1] = min(o.mi[1], tr[r].mi[1]);
        o.mx[1] = max(o.mx[1], tr[r].mx[1]);
    }
}

// 构建KD-Tree
int build(int l, int r, int kd) {
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    int k = ++cur;
    nth_element(p + l, p + mid, p + r + 1, [kd](const Point& a, const Point& b) {
        return Cmp(a, b, kd);
    });
    tr[k].tp = p[mid];
    tr[k].ls = build(l, mid - 1, kd ^ 1);
    tr[k].rs = build(mid + 1, r, kd ^ 1);
    update(k);
    return k;
}

// 计算平方距离
db dist_sq(const Point& a, const Point& b) {
    db dx = a.x[0] - b.x[0];
    db dy = a.x[1] - b.x[1];
    return dx * dx + dy * dy;
}

// 计算点到矩形的最小平方距离（剪枝用）
db min_dist_sq(const Point& p, const Node& node) {
    db res = 0;
    for (int i = 0; i < 2; ++i) {
        if (p.x[i] < node.mi[i]) {
            db d = node.mi[i] - p.x[i];
            res += d * d;
        } else if (p.x[i] > node.mx[i]) {
            db d = p.x[i] - node.mx[i];
            res += d * d;
        }
    }
    return res;
}

// 计算点到矩形的最大平方距离（剪枝用）
db max_dist_sq(const Point& p, const Node& node) {
    db res = 0;
    for (int i = 0; i < 2; ++i) {
        db d1 = p.x[i] - node.mi[i];
        db d2 = node.mx[i] - p.x[i];
        res += max(d1 * d1, d2 * d2);
    }
    return res;
}

// 查询最近邻
void query_min(const Point& p, int k) {
    if (!(p.x[0] == tr[k].tp.x[0] && p.x[1] == tr[k].tp.x[1])) {
        ans_min_sq = min(ans_min_sq, dist_sq(p, tr[k].tp));
    }
    int l = tr[k].ls, r = tr[k].rs;
    db dl = (l ? min_dist_sq(p, tr[l]) : 1e20);
    db dr = (r ? min_dist_sq(p, tr[r]) : 1e20);
    if (dl < dr) {
        if (dl < ans_min_sq) query_min(p, l);
        if (dr < ans_min_sq) query_min(p, r);
    } else {
        if (dr < ans_min_sq) query_min(p, r);
        if (dl < ans_min_sq) query_min(p, l);
    }
}

// 查询最远邻
void query_max(const Point& p, int k) {
    ans_max_sq = max(ans_max_sq, dist_sq(p, tr[k].tp));
    int l = tr[k].ls, r = tr[k].rs;
    db dl = (l ? max_dist_sq(p, tr[l]) : -1);
    db dr = (r ? max_dist_sq(p, tr[r]) : -1);
    if (dl > dr) {
        if (dl > ans_max_sq) query_max(p, l);
        if (dr > ans_max_sq) query_max(p, r);
    } else {
        if (dr > ans_max_sq) query_max(p, r);
        if (dl > ans_max_sq) query_max(p, l);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i].x[0] >> p[i].x[1];
    }
    cur = 0;
    int root = build(0, n - 1, 0);
    ans_min_sq = 1e20;
    ans_max_sq = 0;
    for (int i = 0; i < n; ++i) {
        query_min(p[i], root);
        query_max(p[i], root);
    }
    cout << fixed << setprecision(2) << sqrt(ans_min_sq) << " " << sqrt(ans_max_sq) << endl;
    return 0;
}

关键优化

1. 平方距离计算：避免重复开方，最后统一开方输出
2. 高效剪枝：利用包围盒的最小/最大可能距离提前终止搜索
3. 搜索顺序：优先搜索更可能包含最优解的子树
4. 内存优化：直接使用数组存储，减少指针开销

复杂度分析

• 平均复杂度：$O(n \log n)$
• 最坏复杂度：$O(n^2)$（但实际表现良好）
• 空间复杂度：$O(n)$

该算法能够高效处理 $10^5$ 规模的点集，满足题目要求。