Пошук, сортування та поняття складності у програмуванні, Детальна інформація
Пошук, сортування та поняття складності у програмуванні
Сортування за неспаданням координати Y – результатом є масив B, такий, що A[B[1]].Y<= … <= A[B[n]].Y;
Вибір початкової точки:
k:=2; km:=1; ym:=a[b[1]].y; xm:=a[b[1]].x;
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
Вибір початкової точки:
k:=2; km:=1; ym:=a[b[1]].y; xm:=a[b[1]].x;
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
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021