Пошук, сортування та поняття складності, Детальна інформація

while (k<=n) and (a[b[k]].y=ym)do

begin

if a[b[k]].x < xm then

begin km:=k; xm:=a[b[k]].x end;

k:=k+1

end;

swap(b[1], b[km]);

end;

function left ( tp : pnt ) : boolean;

var x1, y1, x2, y2, x3, y3 : real;

begin

y1:=a[c[ll-1]].y; y2:=a[c[ll]].y; y3:=tp.y;

x1:=a[c[ll-1]].x; x2:=a[c[ll]].x; x3:=tp.x;

if (y3=y2) and (x3=x2) then

left:=false else

if (y2=y1) and (y3=y2) then

left:=( (x2-x1)*(x3-x2)>0 ) or ( x3-x2<0 )

else

left:=( (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)>=0 )

end;

function right ( tp : pnt ) : boolean;

var x1, y1, x2, y2, x3, y3 : real;

begin

y1:=a[c[rr+1]].y; y2:=a[c[rr]].y; y3:=tp.y;

x1:=a[c[rr+1]].x; x2:=a[c[rr]].x; x3:=tp.x;

if (y3=y2) and (x3=x2) then

right:=false else

if (y2=y1) and (y3=y2) then

right:=( (x2-x1)*(x3-x2)>0 ) or ( x3-x2>0 )

else right:=( (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)<=0 )