凸包(旋转卡壳)

大概理解了凸包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<n; p++)
{
while(cross(ch[p+1],ch[q+1],ch[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-2187 Beauty Contest,旋转卡壳求解平面最远点对!-LMLPHPPOJ-2187 Beauty Contest,旋转卡壳求解平面最远点对!-LMLPHP 
 POJ-2187 Beauty Contest,旋转卡壳求解平面最远点对!-LMLPHPPOJ-2187 Beauty Contest,旋转卡壳求解平面最远点对!-LMLPHP 

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])<dis(p2,a[0]))) return 1;
return 0;
}
void Graham()//先求凸包;
{
int k=0;
for(int i=0; i<n; i++)
if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x)) k=i;
swap(a[0],a[k]);
sort(a+1,a+n,cmp);
tot=2,p[0]=a[0],p[1]=a[1];
for(int i=2; i<n; i++)
{
while(tot>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<tot; i++)
{
while(multi(p[i+1],p[q+1],p[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<n; i++) scanf("%d%d",&a[i].x,&a[i].y);
int ans=solve();
printf("%d\n",ans);
}
return 0;
}

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

05-11 11:15