KD树，来源计算几何，在《计算几何-算法与应用》一书中有详细的解释。

　　这题是比较裸的KD树模型，要在点集中找到离一个点最近的一个点。其实KD树就是一棵多维平衡二叉树，将多维空间分成很多个部分，查找时能够较快的逼近查找点，从而快速的找到距离某点最近或者较近的点。

　　在网上找到了这份模版，简洁高效。

　　MARK一下URAL1369，也是一道KD树，目前TLE中。。。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAXN 100005 5 #define INF (1LL<<62) 6 using namespace std; 7 typedef long long LL; 8 struct point{ 9     int x,y;10 }p[MAXN],p2[MAXN];11 bool dv[MAXN];12 bool cmpx(const point& p1,const point& p2){13     return p1.x
        
         >1;24     //按照坐标范围选择建树轴25     int minx=min_element(p+l,p+r,cmpx)->x;26     int miny=min_element(p+l,p+r,cmpy)->y;27     int maxx=max_element(p+l,p+r,cmpx)->x;28     int maxy=max_element(p+l,p+r,cmpy)->y;29     dv[mid]=(maxx-minx>=maxy-miny);30     //dv[mid]=(step&1);也可以按照层数交替建树,貌似效率略慢31     nth_element(p+l,p+mid,p+r,dv[mid]?cmpx:cmpy);32     buildKD(l,mid,p);33     buildKD(mid+1,r,p);34 }35 LL res=0;36 void find(int l,int r,point a,point p[]){37     if(l==r)return;38     int mid=(l+r)>>1;39     LL dist=getdis(a,p[mid]);40     if(dist>0)res=min(res,dist);41     LL d=dv[mid]?(a.x-p[mid].x):(a.y-p[mid].y);42     int l1=l,l2=mid+1,r1=mid,r2=r;43     if(d>0)swap(l1,l2),swap(r1,r2);44     find(l1,r1,a,p);45     if(d*d