, y i ) - ( x , y ) лежатиме поза кута, утвореного зазначеними векторами, лівіше нього. Тоді векторний добуток ( x i +1 - x i ) ( y - Y i ) - ( y i +1 - y i ) ( x - X i ) Ві 0, для будь-якої точки ( x , y ), ще не що увійшла в кордон опуклої оболонки. Отже, ми можемо спочатку вважати наступної, ( i + 1)-ой, будь-яку, ще не ввійшла в опуклу оболонку, точку, а потім, обчислюємо вказане вираз для інших "вільних" точок ( х , y ). Якщо для однієї з них ( x i +1 - x i ) ( y - Y i ) - ( y i +1 - y i ) ( x - X i ) <0, вважаємо наступною її і продовжуємо перевірку інших точок (аналогічно алгоритму пошуку мінімального елемента в масиві). Якщо ж значення виразу дорівнює 0, то порівнюємо квадрати довжин векторів, а саме ( x i +1 - x i ) 2 + ( Y i +1 - y i ) 2 і ( x - X i ) 2 + ( y - y i ) 2 . p> Таким чином, при вирішенні даної задачі у випадку спочатку цілочисельних координат ми повністю можемо уникнути застосування речової арифметики, а, отже, позбутися від втрати точності обчислень. В іншому випадку, у вирішення можуть бути включені "зайві" точки, близькі до кордону опуклої оболонки або не враховано деякі з "потрібних" точок. Складність даного алгоритму складе O ( kN ), де k - кількість точок в опуклій оболонці, в гіршому випадку рівне N . Існують алгоритми вирішення цього завдання, засновані на попередній сортуванні точок вихідного безлічі, наприклад, за значенням кута в полярній системі координат з центром в одній з точок опуклої оболонки, з обчислювальною складністю O ( N log N ) (алгоритм Грехема). Те є найбільш трудомістким завданням виявляється саме сортування вихідних точок.
Наведемо програму вирішення даної задачі алгоритмом Джарвіса:
var a, b: array [1 .. 100] of record
x, y: integer ;
f: boolean
end;
min, m, j, k, n: integer ;
begin
readln (n);
for i: = 1 to n do
begin
read (a [i]. x, a [i]. y);
a [i]. f: = false
end ;
{шукаємо нижню праву точку}
m: = 1;
for i: = 2 to n do
if a [i]. y then m: = i else
if (a [i]. y = a [m]. y) and
(a [i]. x> a [m]. x) then m: = i;
b [1]: = a [m];
a [m]. f: = true ;
k: = 1;
repeat
min: = 1;
{шукаємо першу ще вільну точку}
while a [min]. f do inc (min);
{шукаємо чергову вершину опуклої оболонки}
for j: = 1 to n do
if ( not a [j]. f) and
((a [min]. x-b [k]. x) * (a [j]. y-b [k]. y) -
(a [j]. x-b [k]. x) * (a [min]. y-b [k]. y) <0)
then min: = j else
if ( not a [j]. f) and
((a [min]. x-b [k]. x) * (a [j]. y-b [k]. y) -
(a [j]. x-b [k]. x) * (a [min]. y-b [k]. y) = 0) and
(sqr (a [min]. xb [k]. x) + sqr (a [min]. yb [k]. y)>
sqr (a [j]. x-b [k]. x) + sqr (a [j]. y-b [k]. y))
then min: = j;
k: = k +1;
a [min]. f: = true ;
b [k]: = a [min] {Записана чергова вершина}
until min = m; {поки ламана НЕ замкнеться}
for j: = 1 to k do {Друк результату}
writeln (b [j]. x, ' ', B [j]. Y);
end .
Наведемо приклади завдань, при вирішенні яких використовується побудова опуклої оболонки.
Задача 1. Стіна. ( У англомовному варіанті завдання пропонувалася на студентських командних змаганнях з програмування в Санкт-Петербурзі в 2001 р. )
Одного разу жадібний король наказав своєму архітектору побудувати стіну навколо палацу. Король був настільки жадібний, що не став слухати пропозиції архітектора про побудову стіни досконалої форми. Замість цього король наказав витратити на будівництво стіни певної висоти і довільної форми (не обов'язково у вигляді ламаної!) якомога менше цеглин, але зажадав, щоб стіна відстояла від палацу не менше, аніж на ...
