题目描述

已知平面内 N 个点的坐标，求欧氏距离下的第 K 远点对。

---

输入格式

输入文件第一行为用空格隔开的两个整数 N， K。接下来 N 行，每行两个整数 X,Y，表示一个点

的坐标。1 < =  N < =  100000， 1 < =  K < =  100， K < =  N*(N−1)/2 ， 0 < =  X, Y < 2^31。

---

输出格式

输出文件第一行为一个整数，表示第 K 远点对的距离的平方（一定是个整数）。

---

 

• 题解：

  • 注意只需要保证最大的k个值都被找到就可以确定答案了；
  • 旋转卡壳做法：
  • 平面最近点对可以通过求出凸包之后(特判一下一条直线)卡壳得到；
  • 这样求$min(n-1,k)$次最远点对；
  • 每求一次，就将求出的点对删掉，将和它们相关的距离放进小顶堆中，多于$k$个就丢掉最小值；
  • 答案就是堆顶；
  • 当做到最远距离已经<=堆顶时就可以break了;
  • 复杂度：$O(NlogN+NKlogK)$
• 1 #include
          
            2 #define ll long long  3 using namespace std; 4 const int N=100010;  5 int n,m,WD,mn[N][2],mx[N][2],ch[N][2],rt; 6 struct P{ 7     int x,y; 8     P(int _x=0,int _y=0):x(_x),y(_y){}; 9     P operator -(const P&a)const{
        return P(x-a.x,y-a.y);}10     bool operator <(const P&a)const{
        return WD?y
           
            
             ,greater
             
               >ans;13 ll len(P a){
        return (ll)a.x*a.x+(ll)a.y*a.y;} 14 void build(int&k,int l,int r,int d){15     k=(l+r)>>1;16     WD=d;nth_element(p+l,p+k,p+r+1);17     mn[k][0]=mx[k][0]=p[k].x;18     mn[k][1]=mx[k][1]=p[k].y;19     if(l
              
               ans.top())ans.pop(),ans.push(tmp);38     ll tl = cal(ch[k][0]), tr = cal(ch[k][1]);39     if(tl>tr){40         if(tl>ans.top())query(ch[k][0]);41         if(tr>ans.top())query(ch[k][1]);42     }else{43         if(tr>ans.top())query(ch[k][1]);44         if(tl>ans.top())query(ch[k][0]);45     }46 }47 int main(){48     #ifndef ONLINE_JUDGE49     freopen("T2.in","r",stdin);50     freopen("T2.out","w",stdout);51     #endif52     scanf("%d%d",&n,&m);53     for(int i=1;i<=n;++i)scanf("%d%d",&p[i].x,&p[i].y);54     for(int i=1;i<=m*2;++i)ans.push(0);55     build(rt,1,n,0);56     for(int i=1;i<=n;++i){q=p[i];query(rt);}57     cout<
               
                <
               
              
             
            
           
          
  • $k-d \ \ tree$做法
  • 同样$k-d$可以支持查找最远点对，精髓在于$kdtree$估价函数的剪枝；
  • 对每个点找一次最远点对，同样放进小顶堆维护；
  • 如果堆大小达到$2*k$（因为此时的点对有序）；
  • 答案就是堆顶；
  • 同样<=堆顶的值就对答案无影响了，直接用$kdtree$的估值函数减掉；
  • 复杂度似乎比较玄。。。$O(N\sqrt{N} + N\sqrt{N}logK)$
• 1 #include
          
            2 #define ll long long 3 using namespace std; 4 const int N=100010; 5 int n,k,vis[N],id[N]; 6 priority_queue
           
            
             ,greater
             
               >ans; 7 char gc(){ 8     static char*p1,*p2,s[1000000]; 9     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);10     return(p1==p2)?EOF:*p1++;11 } 12 int rd(){13     int x=0; char c=gc();14     while(c<'0'||c>'9')c=gc();15     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();16     return x;17 }18 struct P{19     int x,y;20     P(int _x=0,int _y=0):x(_x),y(_y){};21     P operator -(const P&a)const{
        return P(x-a.x,y-a.y);}22     bool operator <(const P&a)const{
        return x==a.x?y
              
               
                1&&crs(q[top]-q[top-1],p[i]-q[top])<=0)top--;39 q[++top]=p[i],id[top]=i;40 }41 int now=top;42 i=n;while(vis[i])--i;43 for(--i;i;--i)if(!vis[i]){44 while(top>now&&crs(q[top]-q[top-1],p[i]-q[top])<=0)top--;45 q[++top]=p[i],id[top]=i;46 }47 top--;48 if(top==2){49 vis[id[1]]=vis[id[2]]=1;50 ins(len(q[1]-q[2]));51 } 52 int x = 2;ll mx=-1,pos1,pos2;53 for(i=1;i<=top;++i){54 P A = q[i%top+1]-q[i];55 while(x!=i&&crs(A,q[x%top+1]-q[x])>0)x=x%top+1;56 ll t = len(q[x]-q[i]);57 if(t>mx)mx=t,pos1=id[i],pos2=id[x];58 }59 if(len(p[pos1]-p[pos2])<=ans.top())return false;60 for(i=1;i<=n;++i)if(!vis[i]&&i!=pos1){61 ins(len(p[i]-p[pos1]));62 }63 for(i=1;i<=n;++i)if(!vis[i]&&i!=pos1&&i!=pos2){64 ins(len(p[i]-p[pos2]));65 }66 vis[pos1]=vis[pos2]=1;67 return true;68 }69 int main(){70 freopen("T2.in","r",stdin);71 freopen("T2.out","w",stdout);72 n=rd(),k=rd();73 for(int i=1;i<=n;++i)p[i].x=rd(),p[i].y=rd();74 sort(p+1,p+n+1);75 for(int i=1;i<=k;++i)ans.push(0);76 for(int i=1;i<=min(k,n-1);++i)if(!solve())break;77 cout<
                
                 <