分析：k_d树的模版题，参考了别人的写的；划分的时候采用坐标跨度作为分割依据的效率略比采用树的深度作为划分依据的高；nth_element函数比sort函数的效率高；全部采用getchar和putchar效率也能提高一些。
#include<iostream>#include<algorithm>using namespace std;struct POINT{int x,y;};struct K_D_Node{POINT mid;//分割中点int split_axis;//分割的轴，0为x轴,1为y轴K_D_Node* child[2];//0左子节点，1右子节点};#define N 100100const __int64 inf=0x7fffffffffffffff;POINT p[N],p2[N];K_D_Node K_D_Tree[N];int len;__int64 ans;bool cmpx(const POINT& a,const POINT& b){return a.x<b.x;}bool cmpy(const POINT& a,const POINT& b){return a.y<b.y;}K_D_Node* MallocNode(){K_D_Tree[len].child[0]=K_D_Tree[len].child[1]=NULL;return &K_D_Tree[len++];}K_D_Node* Build_Tree(int L,int R,int depth){int mid,t;K_D_Node* q;int minx,miny,maxx,maxy;if(L>R) return NULL;q=MallocNode();//———————-//t=depth%2;//用树的深度作为分割依据//———————minx=min_element(p+L,p+R,cmpx)->x;//用坐标跨度作为划分依据miny=min_element(p+L,p+R,cmpy)->y;maxx=max_element(p+L,p+R,cmpx)->x;maxy=max_element(p+L,p+R,cmpy)->y;if(maxx-minx>=maxy-miny)t=0;elset=1;q->split_axis=t;if(L==R){q->mid=p[L];return q;}mid=(L+R)>>1;if(t==0)//以x轴分割nth_element(p+L,p+mid,p+R+1,cmpx);//sort(p+L,p+R+1,cmpx);elsenth_element(p+L,p+mid,p+R+1,cmpy);//sort(p+L,p+R+1,cmpy);q->mid=p[mid];q->child[0]=Build_Tree(L,mid-1,depth+1); //构建左子树q->child[1]=Build_Tree(mid+1,R,depth+1);return q;}__int64 DIS(const POINT& a,const POINT& b){__int64 xx,yy;xx=a.x-b.x;yy=a.y-b.y;return (__int64)xx*xx+(__int64)yy*yy;}void Query(K_D_Node* q,const POINT& a){int tmp,s;__int64 dis;//距离平方if(q==NULL) return ;if(q->split_axis==0)//X轴{tmp=q->mid.x;s=a.x;}else//Y轴{tmp=q->mid.y;s=a.y;}if(s<=tmp)Query(q->child[0],a); //左子树elseQuery(q->child[1],a);dis=DIS(q->mid,a);if(dis && dis<ans)//注意这里必须要是dis不等于0才更新,避免处理到自身点,如果输入中有重复点则不能处理ans=dis;if((__int64)(tmp-s)*(tmp-s)<ans) //可能在另一半中，，查找另一半{if(s<=tmp)Query(q->child[1],a);elseQuery(q->child[0],a);}}int ReadInt() {int ans;char c;c=getchar();while(c<'0' || c>'9') c=getchar();ans=c-'0';while((c=getchar())>='0' && c<='9'){ans=ans*10+c-'0';}return ans; }void PutInt64(__int64 x) {int b[32],i;i=0;while(x){b[i++]=x%10;x/=10;}for(i–;i>=0;i–)putchar(b[i]+'0'); }int main(){int t,n,i;K_D_Node* root;t=ReadInt();while(t–){n=ReadInt();for(i=0;i<n;i++){p[i].x=ReadInt();p[i].y=ReadInt();p2[i]=p[i];}len=0;root=Build_Tree(0,n-1,0); //建立k_d树for(i=0;i<n;i++){ans=inf;Query(root,p2[i]);PutInt64(ans);putchar('\n');}}return 0;}
伟人之所以伟大，是因为他与别人共处逆境时，
