凸包（旋转卡壳）

  大概理解了凸包A了两道模板题之后在去吃饭的路上想了想什么叫旋转卡壳呢？回来无聊就搜了一下，结果发现其范围真广。

   凸包：

  凸包就是给定平面图上的一些点集（二维图包），然后求点集组成的凸多边形，但是要包含所有的点。

求凸多边形的方法：Graham算法描述如下:

Graham()算法先对点进行排序，有极角序和水平序两种排序方式。我们仍然以左下方的点作为基准点来通过叉积进行排序。利用STL里面的sort或者自己写个排序算法，排序所用时间为O(NlogN)，极角序列如左图所示：极角排序以参考点为极角坐标系原点 各个点的极角为关键字。水平序如右图所示：以横坐标为第一关键字，纵坐标为第二关键字，排序点集。然后从第一个点开始 分别利用Graham扫描生成左链和右链。Graham的扫描是一个很优美的过程，用到的数据结构也很简单，仅仅是一个栈而已

      核心的思想是按照排好的序，依次加入新点得到新的边。如果和上一条边成左转关系就压栈继续，如果右转就弹栈直到和栈顶两点的边成左转关系 压栈继续。实现的时候我们不用存边，只需要含顺序在栈里存点，相邻两点就是一条边。由于我们时时刻刻都保证栈内是一个凸壳 所以最后扫描完毕，就得到了一个凸包。

     旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。虽然算法的思想不难理解，但是实现起来真的很容易让人“卡壳”。

     旋转卡壳：

   就是枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点，计算这个顶点到该边两个端点的距离，并记录最大的值。直观上这是一个O(n^2)的算法，和直接枚举任意两个顶点一样了。但是注意到当我们逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。于是我们得到了O(n)的算法。

//计算凸包直径，输入凸包ch，顶点个数为n，按逆时针排列，输出直径的平方int rotating_calipers(Point *ch,int n){    int q=1,ans=0;    ch[n]=ch[0];    for(int p=0; p
    
     cross(ch[p+1],ch[q],ch[p])) q=(q+1)%n;        ans=max(ans,max(dist(ch[p],ch[q]),dist(ch[p+1],ch[q+1])));//距离的平方最大值    }    return ans;}
    

Beauty Contest

     POJ上总是有相关的水题，学过就很简单了，但要真的理解其精髓并非容易之事。

     这道题就是求凸包上距离最远的两个点的距离的平方，开始还以为是Manhatten距离，看了看模板才明白。

struct node{    int x,y;} a[N],p[N];int n,tot;int dis(node a,node b){    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int multi(node p0,node p1,node p2){    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int cmp(node p1,node p2)//极角排序；{    int x=multi(p1,p2,a[0]);    if(x>0||(x==0&&dis(p1,a[0])
    
     1&&multi(a[i],p[tot-1],p[tot-2])>=0) tot--;        p[tot++]=a[i];    }}int solve(){    Graham();    int q=1,ans=0;    p[tot]=p[0];    for(int i=0; i
     
      multi(p[i+1],p[q],p[i])) q=(q+1)%tot;        ans=max(ans,max(dis(p[i],p[q]),dis(p[(i+1)%tot],p[(q+1)%tot])));    }    return ans;}int main(){    while(~scanf("%d",&n))    {        for(int i=0; i
     
    

 一天做了3道算法题+一道CF-D，小有成就感。还在慢慢进步，永不止步勇往直前！