Після обробки послідовності нова точка додається до неї. Виключенням є випадок, коли нова точка лежить на відрізку між останніми точками лівої та правої послідовностей обходу. Перевірити це дуже просто, оскільки з упорядкованості точок за координатою Y випливає, що такий відрізок може бути лише горизонтальним.

Симетричним чином точка додається (або не додається) до правої послідовності.

Упорядкованість точок по вертикалі забезпечує, що при обробці нової точки не виникає одночасно лівого повороту до неї з кінця лівої послідовності та правого – з правої. Крім того, якщо точка була кінцевою в обох послідовностях, то після обробки наступної точки вона буде вилучена принаймні з однієї з них. Упорядкованість також гарантує, що необроблені точки лежать не нижче від тих, за якими побудовано поточну оболонку. Врахування усіх цих властивостей суттєво спрощує алгоритм.

Отже, після обробки останньої точки ми маємо ліву та праву послідовності. Результат ми одержимо, друкуючи, наприклад, ліву послідовність з її початку, а потім праву з її кінця. Це відповідає обходу нашого саду ззовні за годинниковою стрілкою.

Перейдемо до реалізації алгоритму. Координати точок подамо масивом структур з полями X і Y. При його сортуванні ми не будемо переставляти місцями значення його елементів, тобто структури. Створимо допоміжний масив індексів і відсортуємо його так, щоб перше значення в ньому вказувало на структуру з найменшим значенням Y, друге – на структуру з другим за порядком значенням тощо. Наприклад, якщо послідовні структури мають координати Y

10 -1 33 15 0,

то значеннями послідовних елементів допоміжного масиву є номери структур у їх упорядкуванні:

2 5 1 4 3.

У сортуванні масиву структур A за їх координатою Y з допоміжним індексовим масивом замість порівнянь полів та обмінів значень елементів A[i] та A[k] відбуваються порівняння елементів A[B[i]].Y і A[B[k]].Y та обміни значень B[i] і B[k].

Після сортування відшукаємо початкову точку – з найменшою координатою X серед тих, що мають найменшу координату Y.

Ліву та праву послідовності зберігатимемо в додатковому масиві індексів. Ліва заповнює його з початку, права – з кінця. Нехай всього точок n. Посилання на початкову точку запам'ятаємо двічі в крайніх елементах масиву. З точок, що залишилися, лише остання може з'явитися в обох послідовностях одночасно. Тому для них достатньо n елементів масиву. Отже, всього нам потрібно n+2 елементи.

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

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;

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 )

end;

procedure run;

var k : int; tp : pnt;

begin

c[0]:=b[1]; c[n+1]:=b[1]; c[1]:=b[2]; c[n]:=b[2];

ll:=1; rr:=n;

if n=3 then begin c[n]:=b[3]; exit end;

for k:=3 to n do

begin

tp := a[b[k]];

while (ll>=1) and left(tp) do ll:=ll-1;

if (tp.y > a[c[ll]].y) or (tp.y > a[c[rr]].y)or

not( (tp.x>a[c[ll]].x)and(tp.x<a[c[rr]].x) )

then begin ll:=ll+1; c[ll]:=b[k] end;

while (rr<=n) and right(tp) do rr:=rr+1;

if (tp.y > a[c[ll]].y) or (tp.y > a[c[rr]].y)or

not( (tp.x>a[c[ll]].x)and(tp.x<a[c[rr]].x) )

then begin rr:=rr-1; c[rr]:=b[k] end;

end;

end;

procedure done;

var k : int;

begin

for k:=0 to ll do writeln(a[c[k]].x, ' ', a[c[k]].y);

if not((a[c[ll]].x=a[c[rr]].x)and(a[c[ll]].y=a[c[rr]].y))

then writeln(a[c[rr]].x, ' ', a[c[rr]].y);

for k:=rr+1 to n do

writeln(a[c[k]].x, ' ', a[c[k]].y);

end;

BEGIN

init; run; done

END.

Проаналізуємо складність наведеного алгоритму. Для сортування масиву потрібно O(nlogn) операцій. В процесі побудови оболонки кожна точка додається до послідовностей та вилучається з них не більше, ніж по одному разу. Тому складність власне побудови оболонки лінійна, і весь алгоритм має складність O(nlogn).

Задачі

15. Написати підпрограму підрахунку кількості різних значень елементів числового масиву. Складність підпрограми повинна бути O(nlogn), де n – кількість елементів масиву.

16. Написати підпрограму складності O(nlogn), що задає обчислення

а)перетину; б) симетричної різниці

двох n-елементних числових множин, поданих масивами.

17. Обчислити кількість трикутників, які можна скласти з N відрізків попарно різних додатних довжин, N < 2000. Складність програми не повинна перевищувати O(N2).

18. За N-елементним масивом A та перестановкою p(1), p(2), … , p(N) чисел 1, 2, … , N побудувати масив A[p(1)], A[p(2)], … , A[p(N)]. Допоміжний масив не використовувати.

19. Розглянемо прямокутний масив. Розташуємо елементи кожного рядка за зростанням. Потім розташуємо за зростанням елементи кожного стовпця. Довести, що кожний рядок залишиться впорядкованим.

20. (Задача про два станки) Є n деталей, кожна з яких проходить обробку спочатку на