Реферат: Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

end else

begin

l1^.n:=l2;

l1^.p:=l2;

l2^.n:=l1;

l2^.p:=l1;

ls:=l1;

exit;

end;

x:=(l1^.x+l1^.n^.x+l1^.n^.n^.x)/3;

y:=(l1^.y+l1^.n^.y+l1^.n^.n^.y)/3;

r:=l1;

r^.a:=arc((r^.x-x),(r^.y-y));

t:=l1;

repeat

t^.a:=arc((t^.x-x),(t^.y-y));

if (r^.a>t^.a) or ((r^.a=t^.a) and (abs(r^.x-x)+abs(r^.y-y)>abs(t^.x-x)+abs(t^.y-y))) then r:=t;

t:=t^.n;

until t=l1;

l1:=r;

l:=l2;

r:=l;

t:=r;

f:=false;

repeat

if (t.x-x)*(r^.y-y)>(r^.x-x)*(t.y-y) then r:=t;

if (t.x-x)*(l^.y-y)<(l^.x-x)*(t.y-y) then l:=t;

f:=f or((x-t^.p^.x)*(t^.y-t^.p^.y)>(t^.x-t^.p^.x)*(y-t^.p^.y));

t:=t^.n;