题意：
求二维平面内n个点的k远点对
题解：
- 很明显是一个kdtree
- 用小顶堆来维护最大的k个值即可
- 不断塞入最大值来更新
- 可以增加一个剪枝 如果子树的最大距离比堆顶小 那就不用继续下去了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; struct point{ll x[2];}t[N],temp[N],a[N]; int mi[N][2],ma[N][2],lson[N],rson[N]; int st[N],top,ncnt,sort_dim,root; bool operator<(point &a,point &b){return a.x[sort_dim]<b.x[sort_dim];}; void up(int x) { for(int i=0;i<=1;i++) { mi[x][i]=ma[x][i]=t[x].x[i]; if(lson[x])mi[x][i]=min(mi[x][i],mi[lson[x]][i]),ma[x][i]=max(ma[x][i],ma[lson[x]][i]); if(rson[x])mi[x][i]=min(mi[x][i],mi[rson[x]][i]),ma[x][i]=max(ma[x][i],ma[rson[x]][i]); } } void build(int l,int r,int &pos,int dim) { if(l>r)return ; int mid=l+r>>1;pos=++ncnt; sort_dim=dim; nth_element(temp+l,temp+mid,temp+r+1); t[pos]=temp[mid]; build(l,mid-1,lson[pos],dim^1); build(mid+1,r,rson[pos],dim^1); up(pos); } priority_queue<ll,vector<ll>,greater<ll> >q; ll dis(point a,point b){return (a.x[0]-b.x[0])*(a.x[0]-b.x[0])+(a.x[1]-b.x[1])*(a.x[1]-b.x[1]);} ll getdis(point a,int x) { ll ans=0; ans=max(ans,dis(a,(point){mi[x][0],mi[x][1]})); ans=max(ans,dis(a,(point){mi[x][0],ma[x][1]})); ans=max(ans,dis(a,(point){ma[x][0],mi[x][1]})); ans=max(ans,dis(a,(point){ma[x][0],ma[x][1]})); return ans; } void qk(int x,point a) { ll d=dis(a,t[x]); if(d>q.top())q.pop(),q.push(d); if(lson[x]){d=getdis(a,lson[x]);if(d>q.top())qk(lson[x],a);} if(rson[x]){d=getdis(a,rson[x]);if(d>q.top())qk(rson[x],a);} }int k,n; int main() { cin>>n>>k; for(int i=1;i<=n;i++)scanf("%d%d",&temp[i].x[0],&temp[i].x[1]),a[i]=temp[i]; build(1,n,root,0); for(int i=1;i<=2*k;i++)q.push(0); for(int i=1;i<=n;i++)qk(root,a[i]); cout<<q.top(); return 0; }