题目链接：

题意：

给你n个点，让你输出每个点到最近点的欧式距离。

题解：

KD-树裸题，板子抄的鸟神的。

1 #include
      
        2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 using namespace std; 4 using ll=long long; 5  6 namespace KD_Tree{ 7     const int N=1e5+7,DI=2; 8     struct Node{ 9         int p[DI],f,l,r,mx[DI],mi[DI];10         int operator[](const int&idx)const{
    return p[idx];}11         void in(int idx,int *v){f=idx;F(i,0,DI-1)p[i]=v[i];}12         void up(Node&a){13             F(i,0,DI-1){14                 mi[i]=min(mi[i],a.mi[i]);15                 mx[i]=max(mx[i],a.mx[i]);16             }17         }18     }T[N];19     int idx[N],cmpd,root;20     21     bool cmp(const Node&a,const Node&b){
    return a[cmpd]
       
        >1;29         cmpd=d%DI,nth_element(T+l,T+mid,T+r+1,cmp);30         idx[T[mid].f]=mid,T[mid].f=f;31         F(i,0,DI-1)T[mid].mi[i]=T[mid].mx[i]=T[f][i];32         T[mid].l=l!=mid?build(l,mid-1,d+1,mid):0;33         T[mid].r=r!=mid?build(mid+1,r,d+1,mid):0;34         return up(mid),mid;35     }36     ll dist(ll x,ll y=0){
    return x*x+y*y;}37     ll query(ll x,ll y,ll&ans,int rt=root,int d=0)38     {39         ll tmp=dist(x-T[rt][0],y-T[rt][1]);40         if(tmp)ans=min(ans,tmp);41         if(T[rt].l&&T[rt].r)42         {43             bool is=!d?(x<=T[rt][0]):(y<=T[rt][1]);44             ll dis=!d?dist(x-T[rt][0]):dist(y-T[rt][1]);45             query(x,y,ans,is?T[rt].l:T[rt].r,!d);46             if(dis