凸包的Andrew算法模板
前段时间学习了一下凸包,网上主要用的是Graham扫描法,但是dwj说Andrew其实会好一点。然后我自己也看了这两种算法,感觉Andrew其实是后者的改进版,虽然没那么容易理解。
Andrew的算法流程大概如下:
1、把所有的点按照横坐标增序,纵坐标第二关键字增序的顺序排序。编上编号1到N。
2、先把点1加入栈U中,然后顺序往下找点,当U中点数大于等于2时开始判断,如果新加入的点在凸包当前前进方向的顺时针方向,就把新的点加入U,否则U中的点依次退栈,直到U中只剩一个点或者新的点在顺时针方向。
3、把点N加入栈L中,类似于上面的方法倒序找点,找到1号点为止。
4、栈U和L中的所有点即为凸包上的点。
简单证明一下:
1、显然在所有的点中,最左边和最右边(横坐标最小和最大)的点一定在凸包之上。
2、排序完毕后点1和点N一定在凸包上。
3、当前进时出现三点共线,根据凸包最简的原则要去掉直线中间的点(当然有时根据题目要求可以更改)。
4、前进时遇到有点在逆时针方向,说明出现了凹多边形,显然凹进去的那个点就应该排除在外了。
代码:
var a:array[0..100000,1..2]of longint; u,l:array[0..100000]of longint; n,m,i,j,k:longint; ans:extended; procedure sort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(l+r) div 2,1]; y:=a[(l+r) shr 1,2]; repeat while (a[i,1]<x ) or (a[i,1]=x) and (a[i,2]<y) do inc(i); while (x<a[j,1]) or (a[j,1]=x) and (a[j,2]>y) do dec(j); if not(i>j) then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; function cross(x,y,z:longint):longint; //叉积,用来判断两个向量的前进方向。 var x1,y1,x2,y2:longint; begin x1:=a[y,1]-a[x,1]; y1:=a[y,2]-a[x,2]; x2:=a[z,1]-a[y,1]; y2:=a[z,2]-a[y,2]; exit(x1*y2-x2*y1); end; function dis(x,y:longint):extended; begin exit(sqrt(sqr(a[x,1]-a[y,1])+sqr(a[x,2]-a[y,2]))); end; begin read(n); for i:=1 to n do read(a[i,1],a[i,2]); sort(1,n); for i:=1 to n do begin while (u[0]>=2) and (cross(u[u[0]-1],u[u[0]],i)>=0) do dec(u[0]); inc(u[0]); u[u[0]]:=i; end; for i:=n downto 1 do begin while (l[0]>=2) and (cross(l[l[0]-1],l[l[0]],i)>=0) do dec(l[0]); inc(l[0]); l[l[0]]:=i; end; for i:=2 to u[0] do //这里是计算凸包的周长。 ans:=ans+dis(u[i],u[i-1]); for i:=2 to l[0] do ans:=ans+dis(l[i],l[i-1]); writeln(ans:0:1); end. </j></x>
发表回复