简介：
将空间内的点进行合理划分，以支持有关高维点的操作。
维护：
KD-Tree虽然很像线段树，但其实还是一棵二叉搜索树。
对于每个树点x，它维护的东西有：
- $ls_x /rs_x$：它在二叉搜索树上的两个儿子。
- $node_x$：它对应的空间点。
- $S_x$：一个最小的矩形，包含它子树中所有空间点。
建树：
假设我们要对K维空间中的若干个点建树。设已经递归了i层，对应的空间点是$P_{lcdots r}$，来到了二叉搜索树的点x。
我们按第$i\% K$维坐标对点排序，令$node_x =P_{mid=frac{l+r}{2}}$，然后递归处理$(ls_x , P_{l,mid-1})$和$(rs_x , P_{mid+1,r})$，最后令$S_x = S_{ls_x }cup S_{rs_x }$。
复杂度$O(nlog{n})$。
查询：
假设我们要查询空间中距离给定点p最远的点。设当前来到了二叉搜索树的点x。
先用$node_x$与p的距离更新答案，然后计算$S_{ls_x} /S_{rs_x} $对应的四个边界点与点p的距离，取最大值$maxl/maxr$。
如果$maxl/maxr$比当前答案小，则不递归$ls/rs$。否则先递归$max$值大的那一边。
复杂度期望$O(sqrt{n})$。
代码（[CQOI2016]K远点对）：
#include<bits/stdc++.h> #define maxn 100005 #define maxm 500005 #define inf 1ll<<62 #define ll long long #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; struct node{int x[2];}p[maxn]; int n,K,np,tot,ls[maxn],rs[maxn]; int id[maxn],mx[maxn][2],mn[maxn][2]; priority_queue<ll,vector<ll>,greater<ll> > q; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline ll dis(ll xa,ll ya,ll xb,ll yb){return (xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);} inline bool cmp(node a,node b){ if(!np) return (a.x[0]==b.x[0])?(a.x[1]<b.x[1]):(a.x[0]<b.x[0]); else return (a.x[1]==b.x[1])?(a.x[0]==b.x[0]):(a.x[1]<b.x[1]); } inline ll getdis(node po,int k){ ll res=0; for(int i=0;i<2;i++){ ll a=abs(po.x[i]-mx[k][i]),b=abs(po.x[i]-mn[k][i]); res+=max(a*a,b*b); } return res; } inline void pushup(int k){ for(int i=0;i<2;i++){ mn[k][i]=mx[k][i]=p[id[k]].x[i]; if(ls[k]) mn[k][i]=min(mn[k][i],mn[ls[k]][i]),mx[k][i]=max(mx[k][i],mx[ls[k]][i]); if(rs[k]) mn[k][i]=min(mn[k][i],mn[rs[k]][i]),mx[k][i]=max(mx[k][i],mx[rs[k]][i]); } } inline int build(int l,int r,int op){ if(l>r) return 0; int mid=l+r>>1,k=++tot; np=op,id[k]=mid; nth_element(p+l,p+mid,p+1+r,cmp); ls[k]=build(l,mid-1,op^1); rs[k]=build(mid+1,r,op^1); pushup(k); return k; } inline void query(node po,int k){ ll d=dis(po.x[0],po.x[1],p[id[k]].x[0],p[id[k]].x[1]); if(d>q.top()) q.pop(),q.push(d); ll dl=-inf,dr=-inf; if(ls[k]) dl=getdis(po,ls[k]); if(rs[k]) dr=getdis(po,rs[k]); if(dl>dr){ if(dl>q.top()) query(po,ls[k]); if(dr>q.top()) query(po,rs[k]); } else{ if(dr>q.top()) query(po,rs[k]); if(dl>q.top()) query(po,ls[k]); } return; } int main(){ n=read(),K=read(); for(int i=1;i<=n;i++) p[i].x[0]=read(),p[i].x[1]=read(); build(1,n,0); for(int i=1;i<=2*K;i++) q.push(0); for(int i=1;i<=n;i++) query(p[i],1); printf("%lld ",q.top()); return 0; }