凸包的概念

凸包的概念

一个点集Q＝（p0,p1,p2...pn-1)，它的凸包是一个最小的凸多边形P，且满足Q中的每个点或者在P的边界上，或者在P的内部。在直观上，我们可以把Q中的每个点看作露在板外的铁钉．那么凸包就是包含所有铁钉的一个拉紧的橡皮绳所构成的形状．
如图：

2.寻找凸包算法

算法如下(Graham算法):

1)求q中y坐标最小的点p0,若具有最小坐标的点有多个,则取最左边的点作为po.

2)对q中剩余的点按逆时针相对p0的极角排序,若有数个保留其中距p0最远的点

得到序列(p1,p2,...pn-1);

3)p0,p1,p2相继入栈

4)for i=3 to n-1 do

    1) while 由次栈顶元素、栈顶元素和Pi所形成角不是向左转do栈顶元素出栈s；
    2)pi入栈

5)打印按逆时针排列的栈中的各顶点

程序如下:

program tubao;
const maxn=500;
type p=record
     x,y:real;
     end;
var n,top:integer;
list:array[0..maxn]of p;
s:array[1..maxn] of integer;
f:text;
procedure swap(var a,b:p);
var t:p;
begin t:=a;a:=b;b:=t end;
function m(p1,p2,p0:p):real;
begin
m:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
end;
function comp(p1,p2:p):boolean;
var t:real;
begin
t:=m(p1,p2,list[0]);
if (t>0) or (t=0) and (sqr(p1.x-list[0].x)+sqr(p1.y-list[0].y)<
  sqr(p2.x-list[0].x)+sqr(p2.y-list[0].y))
   then comp:=true else  comp:=false;
end;
procedure sort(l,r:integer);
var i,j:integer;
x:p;
begin
if r-l+1<=5 then begin
  for j:=l+1 to  r do
   begin
    i:=j;
    while (i>1) and comp(list,list[i-1]) do
     begin  swap(list,list[i-1]); dec(i) end
   end;
  end else
   begin
    x:=list[l+random(r-l+1)];
    i:=l;j:=r;
    repeat
     while comp(list,x) do inc(j);
     while comp(x,list[j]) do dec(j);
     if i<j then swap(list,list[j])
    until i>=j;
    sort(l,j);
    sort(j+1,r);
    end
end;
procedure init;
var i:integer;
begin
assign(f,'input.txt');
reset(f);
readln(f,n);
for i:=0 to n-1 do
  begin
   readln(f,list.x,list.y);
   if (list.y<list[0].y) or
    (list.y=list[0].y) and (list.x<list[0].x)
    then swap(list[0],list);
   end ;
sort(1,n-1)
end;
procedure graham;
var i:integer;
begin
  for i:=1 to 3 do s:=i-1;
  top:=3;
  for i:=3 to n-1 do
   begin
    while m(list,list[s[top]],list[s[top-1]])>=0 dodec(top);
    inc(top);
    s[top]:=i;
   end;
  for i:=1 to top do
   write('(',list[s].x:7:2,',',list[s].y:7:2,')');
  writeln
end;
begin
init;
graham;
readln
end.