KD樹，來源計算幾何，在《計算幾何-算法與應用》一書中有詳細的解釋。

　　這題是比較裸的KD樹模型，要在點集中找到離一個點最近的一個點。其實KD樹就是一棵多維平衡二叉樹，將多維空間分成很多個部分，查找時能夠較快的逼近查找點，從而快速的找到距離某點最近或者較近的點。

　　在網上找到了這份模版，簡潔高效。

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

1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 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<p2.x; 14 } 15 bool cmpy(const point& p1,const point& p2){ 16 return p1.y<p2.y; 17 } 18 LL getdis(point p1,point p2){ 19 return (LL)(p1.x-p2.x)*(p1.x-p2.x)+(LL)(p1.y-p2.y)*(p1.y-p2.y); 20 } 21 void buildKD(int l,int r,point p[]){ 22 if(l==r)return; 23 int mid=(l+r)>>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<res)find(l2,r2,a,p); 46 } 47 int n,cas; 48 int main(){ 49 freopen("test.in","r",stdin); 50 scanf("%d",&cas); 51 while(cas--){ 52 scanf("%d",&n); 53 for(int i=0;i<n;i++) 54 scanf("%d%d",&p[i].x,&p[i].y),p2[i]=p[i]; 55 buildKD(0,n,p); 56 for(int i=0;i<n;i++){ 57 res=INF; 58 find(0,n,p2[i],p); 59 printf("%I64d\n",res); 60 } 61 62 63 } 64 return 0; 65 }

?

　　

轉載于:https://www.cnblogs.com/swm8023/archive/2012/09/04/2670258.html

總結

以上是生活随笔為你收集整理的HDU 2996 In case of failure [KD树]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。