P1429 平面最近点对（加强版）·kd树

题解

浅谈偏序问题与K-D Tree

---

题目

P1429 平面最近点对（加强版）

---

板子

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, k;

namespace K_D_Tree {

    typedef double dbl;
    const int D = 2;// 空间维度
    int f = 0;//当前遍历到的维度 在kd树建树时相邻层的判断大小的维度是不一样的 x->y->x...


    struct Point {
        dbl d[D];//维度信息 第0维：x,第1维：y,第2维：z....

        // Point[x] = Point.d[x]
        // 不过 struct Point 内部无法使用
        dbl &operator[](const int x) {
            return d[x];
        }

        void read() {
            for (int i = 0; i < D; i++) {
                cin >> d[i];
            }
        }

        bool operator==(const Point &other) {
            for (int i = 0; i < D; i++) {
                if (d[i] != other.d[i]) {
                    return false;
                }
            }
            return true;
        }

        bool operator<(const Point &other) const {
            if (d[f] != other.d[f]) {
                return d[f] < other.d[f]; // 根据当前要求的维度进行排序 用于nth_element()排序中
            }
            // 如果 d[f]==other[f] 就按照维度 找到第一个不相同的维度
            for (int i = 0; i < D; i++) {
                if (i ^ f && d[i] != other.d[i])
                    return d[i] < other.d[i];
            }
            return false;// 到这里其实就是两个重合的点
        }

        //D=2时的构造函数
        Point(dbl x = 0, dbl y = 0) {
            d[0] = x, d[1] = y;
        }

    } p[N]; // 这里的数组p用来存储题目给出的点的信息

    // 求两点距离的平方
#define sqr(x) (pow((x),2.0))

    dbl dis2(Point a, Point b) {
        dbl res = 0.0;
        for (int i = 0; i < D; i++) {
            res += sqr(a[i] - b[i]);
        }
        return res;
    }


    struct KDTree {
    private:

        struct Node {
            Node *son[2];//左右儿子节点
            Point p;// 当前节点存储的点
            Point Min, Max; // 以当前节点为根的子树所代表的矩阵的左下角和右上角

            void pushUp() {//更新儿子传上来的信息 维护子树所代表的矩阵范围
                for (int i = 0; i < D; i++) {
                    Min[i] = min(p[i], min(son[0]->Min[i], son[1]->Min[i]));
                    Max[i] = max(p[i], max(son[0]->Max[i], son[1]->Max[i]));
                }
            }

            // 估值函数 判断目标点到当前矩阵的最短曼哈顿距离的平方
            dbl f(Point x) {
                dbl res = 0.0;
                for (int i = 0; i < D; i++) {
                    res += sqr(max(Min[i] - x[i], 0.0)) + sqr(max(x[i] - Max[i], 0.0));
                }
                return res;
            }

        } *tail, *null, *root, MemoryPool[N];
        // tail - 指向当前存储的最后一个节点的后一个位置
        // null - 自定义的空指针(Min、Max有限定) 注意与NULL的区分
        // MemoryPool - 又找了个空间存之前读入的数组p

        void init() {
            tail = MemoryPool;
            null = tail++;
            null->son[0] = null->son[1] = null;// 都是指向null的
            // null的特殊赋值
            for (int i = 0; i < D; i++) {
                null->Min[i] = DBL_MAX;
                null->Max[i] = DBL_MIN;
            }
            root = null;
        }

        Node *creatNode(Point x) {
            Node *o = tail++;
            o->p = o->Max = o->Min = x;
            o->son[0] = o->son[1] = null;
            return o;
        }


        //根据第d维 对 p[l..r] 内的点进行建树 返回树的根节点
        Node *build(int l, int r, int d) {
            if (l > r) return null;
            int mid = l + r >> 1;
            f = d;
            // 百度nth_element用法
            // 只有p[mid]是在正确的位置上
            nth_element(p + l, p + mid, p + r + 1);
            Node *o = creatNode(p[mid]);//找到中位数
            if (l == r) return o;
            o->son[0] = build(l, mid - 1, (d + 1) % D);
            o->son[1] = build(mid + 1, r, (d + 1) % D);
            o->pushUp();
            return o;
        }

        // 求平面上最近点对
        // 遍历每个点x 在k-d-tree里找关于x的最近点
        void queryNearestPointByX(Node *o, const Point &x) {
            ans = min(ans, (Point) x == o->p ? DBL_MAX : dis2(o->p, x));//如果搜到了自己 则不能算入答案
            dbl F[2] = {DBL_MAX, DBL_MAX};//比较左右两棵子树的估值函数
            if (o->son[0] != null) {
                F[0] = o->son[0]->f(x);
            }
            if (o->son[1] != null) {
                F[1] = o->son[1]->f(x);
            }
            int now = F[0] >= F[1];
            // 减枝 如果估计值都比ans大 就没必要往下走
            if (F[now] < ans) {// 优先走较近的那个矩阵
                queryNearestPointByX(o->son[now], x);
            }
            now ^= 1;
            if (F[now] < ans) { // 然后再走另外一颗
                queryNearestPointByX(o->son[now], x);
            }
        }


    public:
        dbl ans = DBL_MAX;

        KDTree() { init(); }

        void build() {
            root = build(1, n, 0);
        }

        void queryNearestPointPair(Point &x) {
            queryNearestPointByX(root, x);
        }

    } kdt;
}
using namespace K_D_Tree;
map<Point, int> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        p[i].read();
        if (++mp[p[i]] > 1) {
            //有重叠点
            cout << fixed << setprecision(4) << 0.0 << endl;
            return 0;
        }
    }
    kdt.build();
    for (int i = 1; i <= n; i++) {
        kdt.queryNearestPointPair(p[i]);
    }
    
    cout << fixed << setprecision(4) << sqrt(kdt.ans) << endl;
    return 0;
}