题解：P16223 【模板】旋转卡壳/最远点对

· · 题解

废话时间

终于让我抢到模板题的题解了。

正文

前置知识

求凸包和平面向量的一些基础运算。

不会求凸包的移步【模板】二维凸包。不会平面向量基本运算的回去重修高中数学必修二。

注意到如果想要解决此类问题，你最好会向量叉乘。

算法思想

旋转卡壳 的核心思想是：

  1. 最远点对一定出现在点集的凸包上。
  2. 利用凸多边形“对踵点对”的性质，通过旋转两条平行线来遍历所有可能的最远点对，从而在 O(N) 时间内完成。

算法步骤

对于每组数据，假设我们已经求好了凸包上的顶点序列，此时遍历每条边 i \to i+1（i=0 \dots m-1，下标模 m），对于每条边：

  1. 重复执行 k++ 直到 k+1 到当前边的距离小于等于 k 到当前边的距离。
  2. 计算点 k 到点 i 的距离 d_1，以及点 k 到点 i+1 的距离 d_2。除此之外还需考察 k+1 与点 i 及 i+1 的答案，以防漏掉等距对踵点。

正确性证明

凸包的必要性

平面点集的直径（最远点对）一定位于凸包的顶点上。考虑使用反证法，若存在两点 P,Q 为直径，且其中某点不是凸包顶点，则它一定在凸包某条边的上或内部区域，此时将该点沿凸包方向外移可得到更远距离，矛盾。因此只需考虑凸包顶点。

旋转卡壳的可行性

对于凸多边形，定义“对踵点对”为存在两条平行支撑线分别经过两个点，且多边形位于两线之间。直径一定出现在某一对对踵点上。

旋转卡壳模拟一对平行线绕多边形旋转一周的过程：固定一条边（支撑线），找到离该边最远的点（即对踵点），然后旋转到下一组边。

考虑利用叉积的正负判断距离的增减趋势：对于边 e_i = \overrightarrow{h_i h_{i+1}}，设当前点为 h_k，若 \text{cross}(\overrightarrow{h_ih_{i+1}},\overrightarrow{h_ih_{k+1}})>\text{cross}(\overrightarrow{h_ih_{i+1}},\overrightarrow{h_ih_{k}})，则 h_{k+1} 比 h_k 离边 e_i 更远，继续前移 k。这一性质保证了对踵点的单调性，从而每个顶点最多被访问 O(1) 次。

但上面一段只能证明保持 k 单调不减是正确的，进而得到复杂度是正确的，似乎并不能证明算法是正确的。但是要证明算法正确就需要用到凸多边形的单峰性。这里不详细展开。

由于我们遍历了所有边，所以应当不会出现遗漏情况。因此算法能够正确输出直径对应的点对。

复杂度证明

代码

最好注意一下精度问题，但是我太懒了，数据没卡我就不改了。如果加强数据了记得踹我。

具体的细节可能与上文有些出入，不过不影响理解。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct pt{
    double x,y,id;
    pt(){x=y=id=0;}
    bool operator< (const pt &a)const{
        if(a.x!=x)return x<a.x;
        return y<a.y;
    }
}p[N],stk[N];
double cross(pt a,pt b,pt c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double dist(pt a,pt b){
    return __builtin_sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int n,top,T;
double ans;
void andrew(){
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        while(top>=2&&cross(stk[top-1],stk[top],p[i])<=0)
            top--;
        stk[++top]=p[i];
    }
    int tmp=top;
    for(int i=n-1;i>=1;i--){
        while(top>tmp&&cross(stk[top-1],stk[top],p[i])<=0)
            top--;
        stk[++top]=p[i];
    }
    top--;
}
void work(){
    if(n==2){
        cout<<0<<" "<<1<<'\n';
        return ;
    }
    if(top==2){
        cout<<stk[1].id-1<<" "<<stk[top].id-1<<'\n';
        return ;
    }
    int ansl=1,ansr=2,j=3;
    for(int lef=1;lef<=top;lef++){
        int rig=(lef+1)%top;
        if(!rig)rig=top;
        while(true){
            int nej=(j+1)%top;
            if(!nej)nej=top;
            double resa=cross(stk[lef],stk[rig],stk[j]);
            double resb=cross(stk[lef],stk[rig],stk[nej]);
            if(resa<resb)j=nej;
            else break;
        }
        if(ans<dist(stk[lef],stk[j]))
            ans=dist(stk[lef],stk[j]),ansl=stk[lef].id,ansr=stk[j].id;
        if(ans<dist(stk[rig],stk[j]))
            ans=dist(stk[rig],stk[j]),ansl=stk[rig].id,ansr=stk[j].id;
        int nej=(j+1)%top;
        if(!nej)nej=top;
        if(ans<dist(stk[lef],stk[nej]))
            ans=dist(stk[lef],stk[nej]),ansl=stk[lef].id,ansr=stk[nej].id;
        if(ans<dist(stk[rig],stk[nej]))
            ans=dist(stk[rig],stk[nej]),ansl=stk[rig].id,ansr=stk[nej].id;
    }
    cout<<ansl-1<<" "<<ansr-1<<'\n';
}
void solve(){
    cin>>n,ans=top=0;
    for(int i=1;i<=n;i++)
        cin>>p[i].x>>p[i].y,p[i].id=i;
    andrew(),work();
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
        solve();
    return 0;
}

感谢阅读。