Description
已知平面内 N 个点的坐标，求欧氏距离下的第 K 远点对。
Input
输入文件第一行为用空格隔开的两个整数 N， K。接下来 N 行，每行两个整数 X,Y，表示一个点
的坐标。1 < = N < = 100000， 1 < = K < = 100， K < = N*(N−1)/2 ， 0 < = X, Y < 2^31。
Output
输出文件第一行为一个整数，表示第 K 远点对的距离的平方（一定是个整数）。
将所有点建成kd树，用堆维护当前已找到的前k大的点对距离，根据已知的第k大距离距离在kd树上搜索即可
#include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<functional> const long long inf=1ll<<62; inline void mins(int&a,int b){if(a>b)a=b;} inline void maxs(int&a,int b){if(a<b)a=b;} inline void maxs(long long&a,long long b){if(a<b)a=b;} inline int max(int a){return a>0?a:0;} std::priority_queue<long long,std::vector<long long>,std::greater<long long> >mxs; int n,k; int X[2]; inline int read(){ int x=0,c=getchar(); while(c>57||c<48)c=getchar(); while(c>47&&c<58)x=x*10+c-48,c=getchar(); return x; } inline long long dis(long long x,long long y){ return x*x+y*y; } inline void upds(long long x){ if(x<mxs.top())return; mxs.pop(); mxs.push(x); } struct node{ int x[2],mn[2],mx[2]; node*c[2],*f; inline void set(int x1,int x2){ x[0]=mn[0]=mx[0]=x1; x[1]=mn[1]=mx[1]=x2; } inline void upd(){ for(int i=0;i<2;i++)if(c[i]){ for(int j=0;j<2;j++){ mins(mn[j],c[i]->mn[j]); maxs(mx[j],c[i]->mx[j]); } } } inline long long maxv(){ if(!this)return -1; return dis(max(X[0]-mn[0])|max(mx[0]-X[0]),max(X[1]-mn[1])|max(mx[1]-X[1])); } void getmax(){ long long a1=-1,a2=-1; upds(dis(x[0]-X[0],x[1]-X[1])); maxs(a1,c[0]->maxv()); maxs(a2,c[1]->maxv()); if(a1>a2){ if(a1>mxs.top())c[0]->getmax(); if(a2>mxs.top())c[1]->getmax(); }else{ if(a2>mxs.top())c[1]->getmax(); if(a1>mxs.top())c[0]->getmax(); } } }ns[100005],*rt; int dx=0; inline bool operator<(const node&a,const node&b){ if(a.x[dx]!=b.x[dx])return a.x[dx]<b.x[dx]; return a.x[dx^1]<b.x[dx^1]; } node*build(node*l,node*r){ if(l==r)return 0; node*m=l+(r-l>>1); std::nth_element(l,m,r); dx^=1; m->c[0]=build(l,m); m->c[1]=build(m+1,r); m->upd(); dx^=1; return m; } int main(){ n=read();k=read()*2; for(int i=0;i<k;i++)mxs.push(0); for(int i=0;i<n;i++)ns[i].set(read(),read()); rt=build(ns,ns+n); for(int i=0;i<n;i++){ X[0]=ns[i].x[0]; X[1]=ns[i].x[1]; rt->getmax(); } printf("%lld",mxs.top()); return 0; }
复杂度不易计算但实际运行效果很好
