kd树 hdu2966 In case of failure

传送门：

题意：给n个点，求对于每一个点到近期点的欧几里德距离的平方。

思路：看鸟神博客学kd树劲啊点击打开链接

kd树事实上是暴力树。，真的。

。

它把一个平面划分成了非常多个小平面。每次划分的根据是平面中按x排序的点的中位数或者是按y排序的点的中位数。

建树的复杂度是稳定O(nlogn)，可是查询就是大暴力了

把平面分成非常多个小平面后，相当于在平面上搜索剪枝。

kd树是一颗二叉树，假如我要查找离(a,b)近期的点，先依照x和y的划分，从kd树根节点出发走到(a,b)所在的平面，然后这个平面中有一个点。通过这个点。就能大致确定近期点的半径范围了。再看这个圈是否和其它的平面有相交部分，假设有，相同的也訪问其它平面部分（说白了就是暴搜。是不是非常暴力。。

求第k近临时还没学会，仅仅学会了求近期。。

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <string>

#include <vector>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#include <functional>

#define fuck(x) cout<<"["<<x<<"]"

#define FIN freopen("input.txt","r",stdin)

#define FOUT freopen("output.txt","w+",stdout)

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int MX = 1e5 + 5;

struct Point {

    int xy[2], l, r, id;

    void read(int i) {

        id = i;

        scanf("%d%d", &xy[0], &xy[1]);

    }

} P[MX];

int cmpw; LL ans;

int idx[MX];

bool cmp(const Point &a, const Point &b) {

    return a.xy[cmpw] < b.xy[cmpw];

}

int build(int l, int r, int w) {

    int m = (l + r) >> 1; cmpw = w;

    nth_element(P + l, P + m, P + 1 + r, cmp);

    idx[P[m].id] = m;

    P[m].l = l != m ? build(l, m - 1, !w) : 0;

    P[m].r = r != m ? build(m + 1, r, !w) : 0;

    return m;

}

LL dist(LL x, LL y = 0) {

    return x * x + y * y;

}

void query(int rt, int w, LL x, LL y) {

    LL temp = dist(x - P[rt].xy[0], y - P[rt].xy[1]);

    if(temp) ans = min(ans, temp);

    if(P[rt].l && P[rt].r) {

        bool sign = !w ? (x <= P[rt].xy[0]) : (y <= P[rt].xy[1]);

        LL d = !w ?

dist(x - P[rt].xy[0]) : dist(y - P[rt].xy[1]);

        query(sign ? P[rt].l : P[rt].r, !w, x, y);

        if(d < ans) query(sign ? P[rt].r : P[rt].l, !w, x, y);

    } else if(P[rt].l) query(P[rt].l, !w, x, y);

    else if(P[rt].r) query(P[rt].r, !w, x, y);

}

int main() {

    int T, n; //FIN;

    scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        for(int i = 1; i <= n; i++) P[i].read(i);

        int rt = build(1, n, 0);

        for(int i = 1; i <= n; i++) {

            ans = 1e18;

            query(rt, 0, P[idx[i]].xy[0], P[idx[i]].xy[1]);

            printf("%I64d\n", ans);

        }

    }

    return 0;

}