凸包的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>

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.