kd树解平面最近点对

早上起来头有点疼，突然就想到能不能用kd树解平面最近点对问题，就找了道题试了一下，结果可以，虽然效率不高，但还是AC了~

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007

题目要求平面上最近点对间距离的一半。

思路如下：先建立一棵树，所有点插入树中，之后为每个点查询其最近点，枚举找到最小值。注意查询的时候不要让点自己跟自己比。个人感觉，这种写法也可以达到O(nlogn)的复杂度。建树分区间的时候，按x,y中跨度大的一个来分，应该就接近O(nlogn)了，不过我太懒了，那种方法之后再试，现在先x,y轮流着来了。

kd树代码如下：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <cstdio>

 #include <cmath>

 #define MAX (101000)

 #define pow(x) ((x)*(x))

 using namespace std;

 int n, idx;

 struct Point{

     double x[];

     bool operator < (const Point &u) const{

         return x[idx] < u.x[idx];

     }

 }po[MAX];

 struct Tree {

     Point p[MAX<<];

     int son[MAX<<];

     bool f[MAX<<];

     int ps[MAX<<];

     void build ( int l , int r , int u = , int dep = )

     {

         if(l > r) return;

         son[u] = r-l;

         son[u<<] = son[u<<|] = -;

         idx = dep%;

         int mid = (l+r)>>;

         nth_element(po+l, po+mid, po+r+);

         p[u] = po[mid], ps[u] = mid;

         build ( l , mid- , u<< , dep+ );

         build ( mid+ , r , u<<| , dep+ );

     }

     double query(Point a, int id, int u = , int dep = ){

         if(son[u] == -) return 1000000000.0;

         double dis = pow(p[u].x[]-a.x[]) + pow(p[u].x[]-a.x[]);

         if(ps[u] == id) dis = 1000000000.0;

         int dim = dep%, fg = ;

         int x = u<<, y = u<<|;

         if(a.x[dim] >= p[u].x[dim]) swap(x, y);

         double tm1 = 1000000000.0, tm2 = 1000000000.0;

         if(~son[x])tm1 = query(a, id, x, dep+);

         if(pow(a.x[dim] - p[u].x[dim]) < tm1) fg = ;

         if(~son[y] && fg) tm2 = query(a, id, y, dep+);

         if(dis > tm1) dis = tm1;

         if(dis > tm2) dis = tm2;

         return dis;

     }

 }kd;

 int main(){

     while(~scanf("%d", &n), n){

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

                 scanf("%lf %lf", &po[i].x[], &po[i].x[]);

         memset(kd.f, , sizeof(kd.f));

         memset(kd.ps, -, sizeof(kd.ps));

         kd.build(, n-);

         double ans = 1000000000.0;

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

             double tm = kd.query(po[i], i);

             if(tm < ans) ans = tm;

         }

         printf("%.2lf\n", sqrt(ans)/);

     }

     return ;

 }