Сторінка
7
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 деталей, кожна з яких проходить обробку спочатку на першому станку, потім на другому. Кожний станок здатний обробляти одночасно одну деталь і готовий до обробки наступної деталі одразу після обробки попередньої. Відомий час обробки кожної деталі на кожному із станків. Упорядкувати деталі таким чином, щоб час від початку обробки першої деталі до закінчення обробки останьої був якнайменшим. Наприклад, якщо перша деталь обробляється на станках 20 і 10 одиниць часу, а друга – 10 і 20, то за порядку деталей (перша, друга) одержимо час 50, а за порядку (друга, перша) – 40.
Завантажити реферат