ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

Наведемо лише необхідні означення. Доповнити їх до програми залишається вправою.

const mx=5000; {максимальна кількість точок}

type int=integer; pnt=record x, y : int end;

var a : array[1 .. mx] of pnt; {масив точок}

b, {індексовий масив}

c : array[0..mx+1]of int; {масив для лівої та правої послід-тей}

n : int; {кількість точок}

ll, rr : int;{індекси останніх елементів посл-тей у масиві c}

…

procedure init;

var k : int; km, xm, ym : int; …

begin

Читання n точок у масив A;

Сортування за неспаданням координати 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;