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 ;
 }