旋转卡壳入门+模板题（POJ 2187）

Dear 丶 2022-05-25 03:38 243阅读 0赞

最初接触旋转卡壳（应该读xuán zhuǎn qiǎ ké）是在CSU上的一道题（这道题至今没A，也不知道是是吗玄学操作，更新：AC了，输出记得用%f），不过这不重要，重要是学到了新知识！

## 一些历史 ##

1978年， M.I. Shamos’s Ph.D. 的论文”Computational Geometry”标志着计算机科学的这一领域的诞生。 当时他发表成果的是一个寻找凸多边形直径的一个非常简单的算法， 即根据多边形的一对点距离的最大值来确定。  
后来直径演化为由一对对踵点对来确定。 Shamos提出了一个简单的 O(n) 时间的算法来确定一个凸 n 角形的对踵点对。 因为他们最多只有 3n/2 对， 直径可以在 O(n) 时间内算出。  
如同Toussaint后来提出的， Shamos的算法就像绕着多边形旋转一对卡壳。 因此就有了术语“旋转卡壳”。 1983年， Toussaint发表了一篇论文， 其中用同样的技术来解决许多问题。 从此， 基于此模型的新算法就确立了， 解决了许多问题。  
他们包括：  
**计算距离**  
凸多边形直径  
凸多边形宽  
凸多边形间最大距离  
凸多边形间最小距离  
**外接矩形**  
最小面积外接矩形  
最小周长外接矩形  
**三角剖分**  
洋葱三角剖分  
螺旋三角剖分  
**四边形剖分**  
凸多边形属性  
合并凸包  
找共切线  
凸多边形交  
临界切线  
凸多边形矢量和  
**最薄截面**  
最薄横截带

--------------------

然后就讲一下旋转卡壳算法思想：**重点内容**

简单来说就是用一对平行线“卡”住凸包进行旋转。

被一对卡壳正好卡住的对应点对称为对踵点（如下图）  
![这里写图片描述][70]  
可以证明对踵点的个数不超过3N/2个 也就是说对踵点的个数是O(N)的  
对踵点的个数也是我们下面解决问题时间复杂度的保证

有两种卡壳情况：  
一、两个平行线正好卡着两个点  
![这里写图片描述][70 1]  
二、分别卡着一条边和一个点  
![这里写图片描述][70 2]  
在第二种情况中 我们可以看到 一个对踵点和对应边之间的距离比其他点到那条边的距离要大  
也就是一个对踵点和对应边所形成的三角形面积是最大的 下面我们会据此得到对踵点的简化求法。

![黄色那个三角形的上顶点就是底边的对踵点][70 3]

根据上面的第二种情况，我们可以得到下面的方法：  
![这里写图片描述][70 4]  
如果qa，qb是凸包上最远两点，必然可以分别过qa，qb画出一对平行线。通过旋转这对平行线，我们可以让它和凸包上的一条边重合,如图中蓝色直线，可以注意到，qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点，计算这个顶点到该边两个端点的距离，并记录最大的值。

直观上这是一个O(n2)的算法，和直接枚举任意两个顶点一样了。

然而我们可以发现 凸包上的点依次与对应边产生的距离成单峰函数（如下图：）  
![这里写图片描述][70 5]  
这个性质就很重要啦。

根据这个凸包的特性，我们注意到逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。于是我们得到了O(n)的算法。这就是所谓的“旋转”吧！  
利用旋转卡壳，我们可以在O（n）的时间内得到凸包的对锺点中的长度最长的点对。  
又由于最远点对必然属于对踵点对集合 ，那么我们先求出凸包 然后求出对踵点对集合 然后选出距离最大的即可。  
那么具体的代码就很容易实现了，利用叉积。

学习就要趁热打铁啦  
一道模板题：[POJ 2187 Beauty Contes][]

AC代码如下：

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    const int MAXN=50000+7;
    
    struct Points{
        int x,y;
        Points(int x=0,int y=0):x(x),y(y){}
    };
    
    typedef Points Vector;
    Vector operator -(Points A,Points B){
        return Vector(A.x-B.x,A.y-B.y);
    }
    int n,m,maxdis;
    Points p[MAXN],ch[MAXN];
    
    int Cross(Vector A,Vector B){
        return A.x*B.y-A.y*B.x;
    }
    
    bool cmp(Points a,Points b){
        bool ret=false;
        if(a.x<b.x||(a.x==b.x&&a.y<b.y)) ret=true;
        return ret;
    }
    void ConvexHull(){
        sort(p,p+n,cmp);
        m=0;
        for(int i=0;i<n;++i){
            while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
            ch[m++]=p[i];
        }
        int k=m;
        for(int i=n-2;i>=0;--i){
            while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
            ch[m++]=p[i];
        }
        if(n>1) m--;
    } 
    
    int dis(Points a,Points b){
        return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
    }
    void rotating_caliper(){
        if(n==3){
            maxdis=max(dis(p[0],p[1]),dis(p[0],p[2]));
            maxdis=max(maxdis,dis(p[1],p[2]));
        }else{
            int j=2;
            for(int i=0;i<m;++i){
                while(abs(Cross(ch[i]-ch[i+1],ch[j]-ch[i+1]))<abs(Cross(ch[i]-ch[i+1],ch[j+1]-ch[i+1]))){
                    j=(j+1)%m;
                }
                maxdis=max(maxdis,dis(ch[i],ch[j]));
            }
        }
    }
    
    int main(){
        cin>>n;
        for(int i=0;i<n;++i){
            cin>>p[i].x>>p[i].y;
        }
        maxdis=-1;
        if(n==2){
            maxdis=dis(p[0],p[1]);
        }else{
            ConvexHull();
            rotating_caliper();
        }
        cout<<maxdis;
        return 0;
    }

[70]: /images/20220525/287628d68da14462961241910c0e5fd7.png
[70 1]: /images/20220525/5dec0d6db236401f8bae5ecf3e232496.png
[70 2]: /images/20220525/90f09c742fde4ef0adfeb6ce6358af13.png
[70 3]: /images/20220525/a2a01042dbd349888a35f8115101eba8.png
[70 4]: /images/20220525/b056c8b468ab443486fed3a953444427.png
[70 5]: /images/20220525/57890db925904a40874091d19d15ffdc.png
[POJ 2187 Beauty Contes]: https://vjudge.net/contest/214418#problem/A