算法竞赛笔记.二维计算几何.旋转卡壳

旋转卡壳算法，通过枚举凸包上某一条边的同时维护其他需要的点，能够在线性时间内求解如凸包直径、最小矩形覆盖等和凸包性质相关的问题。
洛谷 P1452 【模板】旋转卡壳 / [USACO03FALL] Beauty Contest G

double sqr(Point a,Point b,Point c){
    return fabs(    a.x*b.y-a.y*b.x+
                    c.x*a.y-c.y*a.x+
                    b.x*c.y-b.y*c.x
                );
}
int32_t main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;  
    }
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        while(m>=2&&cross(s[m-1],s[m],s[m],p[i])<=0)m--;
        s[++m]=p[i];
    }
    int k=m;
    for(int i=n-1;i>=1;i--){
        while(m>k&&cross(s[m-1],s[m],s[m],p[i])<=0)m--;
        s[++m]=p[i];
    }
    if(m>1)m--;
    if(m==2){
        cout<<dist(s[1],s[2])<<'\n';
        return 0;
    }
    s[m+1]=s[1];
    int ans=0,cur=3;
    for(int i=1;i<=m;i++){
        while(sqr(s[i],s[i+1],s[(cur)%m+1])>=sqr(s[i],s[i+1],s[cur])){
            cur=cur%m+1;
        }
        ans=max(ans,max(dist(s[i],s[cur]),dist(s[i+1],s[cur])));
    }
    cout<<ans<<endl;
    return 0;
}

P3187 [HNOI2007] 最小矩形覆盖

l=2,r=2,t=2;
for(int i=1;i<=m;i++){
    while(sqr(s[i],s[i+1],s[t%m+1])>=sqr(s[i],s[i+1],s[t]))t=t%m+1;
    while(dot(s[i],s[i+1],s[i+1],s[r%m+1])>=dot(s[i],s[i+1],s[i+1],s[r]))r=r%m+1;
    if(i==1)l=r;//把找左侧支撑点的指针 l，先放到当前右侧支撑点 r 的位置上
    while(dot(s[i+1],s[i],s[i],s[l%m+1])>=dot(s[i+1],s[i],s[i],s[l]))l=l%m+1;
    double res=
    (
        dist(s[i],s[i+1])
        +dot(s[i],s[i+1],s[i+1],s[r])/dist(s[i],s[i+1])
        +dot(s[i+1],s[i],s[i],s[l])/dist(s[i],s[i+1])
    )*sqr(s[i],s[i+1],s[t])/dist(s[i],s[i+1]);
    if(res<ans){
        ans=res;
        I=i;L=l;R=r;T=t;
    }
}
printf("%.5f\n",ans);
Point W[4]={};
double len=dist(s[I],s[I+1]);
Vector dir=(s[I+1]-s[I])*(1.0/len);//方向向量
W[0]=s[I]+dir*dot(dir,s[R]-s[I]);
W[3]=s[I]+dir*dot(dir,s[L]-s[I]);
Vector norm={-dir.y,dir.x};//法向量
double len2=sqr(s[I],s[I+1],s[T])/len;
W[1]=W[0]+norm*len2;
W[2]=W[3]+norm*len2;
for(int i=0;i<4;i++){
    printf("%.5f %.5f\n",W[i].x,W[i].y);                    
}