INFOMAN брой 10
{ This is the input data: N; X1 Y1; X2 Y2; ...; Xn Yn;
11
6 0
-6 3
1 7
2 0
5 -3
11 2
5 7
1 2
6 3
9 7
4 6
ОВОЩНА ГРАДИНА
--------------
Един градинар имал овощна градина с N дървета и решил да я огради с
ограда. Оградата трябвало да има форма на многоъгълник, върховете на който
трябвало да са някои от дърветата и всички дървета трябвало да лежат вътре
в този многоъгълник или на страна от него. Да се напише програма, която из-
числява минималната дължина на ограда, с което може да се огради градината.
Дърветата са дадени като точки в равнината.
РЕШЕНИЕ: Ясно е, че ако оградата е с минимална дължина, то ограждащият
многоъгълник ще е изпъкнал, защото ако не е, можем да премахнем поне един
връх при което периметъра на оградата да се намалява. Получаваме класичес-
ката задача за намиране на минимална изпъкнала обвивка на точки в равнина-
та. За тази класическа задача има известни няколко алгоритъма.Някои от тях
се базират на изчисляване на ъгли, а други - само на разстояния и насочени
лица. Преди да пристъпим към алгоритмичната част на проблема, първо трябва
да въведем някои елементи на аналитичната геометрия.Първо разстояние между
две точки (x1,y1) и (x2,y2) се намира по формулата:
R = SQRT( (x1-x2)ý + (y1-y2)ý )
която си е пряко следствие от питагоровата теорема. Ще казваме че посоката
на три точки в равнината е положителна, ако те са дадени в посока обратна
на часовниковата стрелка, отрицателна, ако са по часовниковата и 0 ако три-
те точки лежат на една права. Нека са зададени три точки с координатите си
(x1,y1), (x2,y2), (x3,y3). Тогава посоката им може да се определи със след-
ната формула:
посока = (x1-x2)*(y1+y2) + (x2-x3)*(y2+y3) + (x3-x1)*(y3+y1)
която е пряко следствие от формулата за насочено лице на многоъгълник. Има
и други функции за посока на три точки, но тази се извежда най-лесно. Един
прост метод за намиране на минималната изпълкнала обвивка е следният: Взе-
маме най-лявата точка A и търсим такава друга точка B, че всички останали
точки да са вдясно от правата AB. Тогава отсечката AB е част от минимална-
та обвивка. След това търсим точка C, такава, че всички точки да са вдясно
от BC и т.н. В крайна сметка получаваме изпъкнал многоъгълник ABCD..., кой-
то е търсената обвивка. За да проверим обаче дали всички точки X са вдясно
от една права AB, трябва всички лица ABX да са отрицателни. Проверката ста-
ва за линейно време и намирането на следваща точка става с линеен брой опи-
ти, а броя на точките, които намираме е линеен, което означава, че този ал-
горитъм има сложност от порядъка N*N*N в най-лошия случай. Ето защо ще из-
ползваме друг алгоритъм, който е малко по-сложен, но намира изпъкналата об-
вивка за време N*logN в най-лошия случай, което е многократно по-бързо.
Първо ще сортираме точките в нарастващ ред по X координатата им, като при
равни X координати ще сортираме по Y координатата. Получава се така, че ви-
наги първата точка е най-долната от всички най-леви, а последната (N-тата)
е най-горната от всички най-десни точки. Вижда се, че първата и последната
точка задължително участват в обвивката. Нека имаме един стек, в който ще
натрупваме точките, които изграждат решението. Първоначално пъхаме точка 1
в стека (най-долната от най-левите точки). Нека търсим отрицателна посока
на точките в резултата. Започваме последователно по ред на номерата да пъ-
хаме точките в стека като следим винаги посоката на последните три точки в
стека да е отрицателна. Ако тя не е отрицателна, премахваме от стека точка-
та, която е предпоследна, защото именно тя прави посоката грешна,а това оз-
начава, че тя е вътрешна за обвивката и задължително не участва в нея. Пос-
ледователното пъхане на точките в стека започвайки от следващата след тази
на върха на стека към последната в списъка и проверяването дали получената
до момента обвивка е изпъкнала и премахването на грешната предпоследна точ-
ка когато не е изпъкнала повтаряме докато на върха на стека не попадне пос-
ледната (N-тата,най-лявата и горна) точка. В този момент сме намерили "гор-
ната" половинка на обвивката. Долната търсим по абсолютно същия начин, но
добавяме в стека не следващите точки след тази на върха, а предишните, т.е.
за следваща точка вземаме винаги не следващата вдясно, а следващата вляво.
В резултата на това получаваме и "долната" половинка на обвивката. Естест-
вено точките, които са вече в стека се отбелязват като използвани и не се
разглеждат (освен ако не излязат от стека като грешни). Изчисляването на
дължината на намерената вече обвивка се прави като сума от страните на по-
лучения многоъгълник използвайки дадената по горе формула за разстояние.
}
{$M 16384,0,655360}
CONST MaxN = 500;
InFileName = 'GAR.PAS';
OutFileName = '';
TYPE TPoint = record x,y:longint end;
VAR P: array[1..MaxN] of TPoint;
N: integer;
Ograda: array[1..MaxN] of integer;
Procedure ReadData; { Прочита входните данни N и P[1..N] }
Var F: Text;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N);
for N:= 1 to N do
with P[N] do
ReadLn(F,x,y);
Close(F);
End;
Function Direction(p1,p2,p3:integer): longint;
Begin { Връща посоката на 3-те точки с номера p1, p2 и p3 }
Direction:=
(P[p1].x-P[p2].x)*(P[p1].y+P[p2].y)
+ (P[p2].x-P[p3].x)*(P[p2].y+P[p3].y)
+ (P[p3].x-P[p1].x)*(P[p3].y+P[p1].y);
End;
Function R(p1,p2:integer): real;
Begin
R:= SQRT( sqr(P[p1].x-P[p2].x) + sqr(P[p1].y-P[p2].y) );
End;
Procedure SortPointsByX; { Сортира точките първо по X и на второ място по Y }
Procedure Swap(var a,b:TPoint);
Var Tmp: TPoint;
Begin
Tmp:=a; a:=b; B:=Tmp;
End;
Var I,J: integer;
Begin
for I:= 1 to N-1 do
for J:= I+1 to N do
if (P[J].x < P[I].x) OR
((P[J].x = P[I].x) and (P[J].y < P[I].y)) then
Swap(P[J],P[I]);
End;
Procedure Solve; { Намира минималната обвивка на точките и дължината й }
Var Count, I: integer;
OutF: Text;
Sum: real;
Used: array[1..MaxN] of boolean;
Procedure Add(P:integer); { Добавя точка с номер P в стека }
Begin
Inc(Count); Ograda[Count]:=P;
Used[P]:=true;
End;
Function Last3: longint; { Връща знака на 3-те точки на върха на стека }
Begin
if Count < 3 then Last3:=-1
else Last3:=Direction(Ograda[Count-2],Ograda[Count-1],Ograda[Count]);
End;
Begin
FillChar(Used,SizeOf(Used),false);
Count:=0; Add(1);
{ Find the up part of the cover }
repeat
for I:= Ograda[Count]+1 to N do
if not Used[I] then
begin
Add(I);
while Last3 >= 0 do
begin
Used[Ograda[Count-1]]:=false;
Ograda[Count-1]:=Ograda[Count];
Dec(Count);
end;
end;
until Ograda[Count] = N;
{ Find the down part of the cover }
Used[1]:=false; { Use vertice 1 again in the down part of the cover }
repeat
for I:= Ograda[Count]-1 downto 1 do
if not Used[I] then
begin
Add(I);
while Last3 >= 0 do
begin
Used[Ograda[Count-1]]:=false;
Ograda[Count-1]:=Ograda[Count];
Dec(Count);
end;
end;
until Ograda[Count] = 1;
{ Calculate the length of the found cover }
Sum:=0;
for I:= 1 to Count-1 do
Sum:= Sum + R(Ograda[I],Ograda[I+1]);
Assign(OutF,OutFileName); Rewrite(OutF);
if Frac(Sum)=0 then
WriteLn(OutF,trunc(Sum))
else WriteLn(OutF,trunc(Sum+1));
Close(OutF);
End;
BEGIN
ReadData;
SortPointsByX;
Solve;
END.