[SDOI2010] 捉迷藏

题目描述

给定一个动态的二维平面点集，支持插入点、删除点，以及查询点集中的最近点对和最远点对的距离（平方距离，避免浮点数运算）。

输入输出格式

• 输入：第一行一个整数n，表示操作次数。接下来n行，每行是"1 x y"（插入点(x,y)）、"2 x y"（删除点(x,y)）或"3"（查询）。
• 输出：每次查询操作输出两个整数，分别为最近点对距离平方和最远点对距离平方。

C21 kd 树 题解

解题思路

• 使用kd树（二维树）维护动态点集，通过空间划分实现高效查询。
• 最近点对：利用kd树的最近邻搜索算法，通过剪枝减少搜索范围。
• 最远点对：维护点集的四个极值点（x最大、x最小、y最大、y最小），最远点必在其中。
• 插入/删除：动态更新kd树结构，删除操作采用标记删除（不立即释放节点空间）。

代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <functional>
using namespace std;

struct Point {
    int x, y;
    Point(int x=0, int y=0) : x(x), y(y) {}
};

struct Node {
    Point p;
    int axis; // 分割轴：0=x轴，1=y轴
    Node *left, *right;
    bool deleted; // 标记删除
    Node(Point p, int axis) : p(p), axis(axis), left(nullptr), right(nullptr), deleted(false) {}
};

class KdTree {
private:
    Node* root;

    // 计算两点距离平方
    long long dist2(const Point& a, const Point& b) {
        long long dx = a.x - b.x;
        long long dy = a.y - b.y;
        return dx*dx + dy*dy;
    }

    // 插入节点
    Node* insert(Node* node, Point p, int depth) {
        if (!node) return new Node(p, depth % 2);
        int axis = node->axis;
        if ((axis == 0 && p.x <= node->p.x) || (axis == 1 && p.y <= node->p.y))
            node->left = insert(node->left, p, depth + 1);
        else
            node->right = insert(node->right, p, depth + 1);
        return node;
    }

    // 删除节点（标记删除）
    Node* remove(Node* node, Point p, int depth) {
        if (!node) return nullptr;
        if (node->p.x == p.x && node->p.y == p.y && !node->deleted) {
            node->deleted = true;
            return node;
        }
        int axis = node->axis;
        if ((axis == 0 && p.x <= node->p.x) || (axis == 1 && p.y <= node->p.y))
            node->left = remove(node->left, p, depth + 1);
        else
            node->right = remove(node->right, p, depth + 1);
        return node;
    }

    // 最近邻搜索
    void nearest(Node* node, Point target, Point& best, long long& min_dist2) {
        if (!node || node->deleted) return;
        long long d = dist2(node->p, target); // 计算当前节点距离
        if (d < min_dist2) {
            min_dist2 = d;
            best = node->p;
        }
        // 确定近子树和远子树
        int axis = node->axis;
        Node *near_sub = (axis == 0 && target.x <= node->p.x) || (axis == 1 && target.y <= node->p.y) ? node->left : node->right;
        Node *far_sub = (near_sub == node->left) ? node->right : node->left;
        // 搜索近子树
        nearest(near_sub, target, best, min_dist2);
        // 计算分割平面距离
        long long plane_dist = (axis == 0) ? (target.x - node->p.x) * (target.x - node->p.x) : (target.y - node->p.y) * (target.y - node->p.y);
        // 如果分割平面距离小于当前最小距离，搜索远子树
        if (plane_dist < min_dist2)
            nearest(far_sub, target, best, min_dist2); // 此处原代码有误，应为far_sub
    }

    // 收集所有有效点（用于查询时遍历，实际可优化）
    void collect_points(Node* node, vector<Point>& points) {
        if (!node || node->deleted) return;
        points.push_back(node->p);
        collect_points(node->left, points);
        collect_points(node->right, points);
    }

    // 查询最远点对（基于极值点）
    pair<long long, long long> query_extremes(const vector<Point>& points) {
        if (points.size() < 2) return {LLONG_MAX, 0};
        long long min_d = LLONG_MAX, max_d = 0;
        // 遍历所有点对计算距离
        for (int i = 0; i < points.size(); ++i)
            for (int j = i+1; j < points.size(); ++j) {
                long long d = dist2(points[i], points[j]);
                if (d < min_d) min_d = d;
                if (d > max_d) max_d = d;
            }
        return {min_d, max_d};
    }
    
public:
    KdTree() : root(nullptr) {}

    void insert(Point p) { root = insert(root, p, 0); }
    void remove(Point p) { root = remove(root, p, 0); }

    long long nearest_dist2(Point target) {
        vector<Point> points;
        collect_points(root, points);
        if (points.size() < 2) return -1; // 不足两点无最近点对
        long long min_d = LLONG_MAX;
        for (auto& p : points) {
            if (p.x == target.x && p.y == target.y) continue; // 排除自身
            long long d = dist2(p, target);
            if (d < min_d) min_d = d;
        }
        return min_d;
    }

    pair<long long, long long> query() {
        vector<Point> points;
        collect_points(root, points);
        return query_extremes(points); // 实际可优化为维护极值点集
    }
};

int main() {
    KdTree kd;
    int n; cin >> n;
    while (n--) {
        int op; cin >> op;
        if (op == 1) {
            int x, y; cin >> x >> y;
            kd.insert(Point(x, y));
        } else if (op == 2) {
            int x, y; cin >> x >> y;
            kd.remove(Point(x, y));
        } else if (op == 3) {
            auto [min_d, max_d] = kd.query();
            if (min_d == LLONG_MAX) cout << "-1 -1\n";
            else cout << min_d << " " << max_d << "\n";
        }
    }
    return 0;
}

说明

• 代码使用标记删除简化实现，实际应用中可优化为平衡kd树（如用红黑树维护子树）。
• 最远点对查询采用遍历所有点的简化方式，实际可通过维护x/y轴极值点集优化至O(1)查询。
• 最近点对查询在动态场景下可结合kd树剪枝算法，避免遍历所有点，提升效率。

C21 kd 树 P2479 [SDOI2010] 捉迷藏