INFOMAN брой 7
{ This is the input data:
2
0 0 10 10
10 0 20 10
8
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
5 0 18 11
-------------
ПРАВОЪГЪЛНИЦИ
-------------
Задачата е от втория ден на 10-тата международна
олимпиада по информатика в Португалия през 1998 година.
На една стена са поставени N плаката с правоъгълна форма. Страните на все-
ки от тях са или хоризонтални или вертикални. Всеки правоъгълник може изцяло
или частично да припокрива други правоъгълници.Дължината на границата на обе-
динението на всички правоъгълници наричаме "периметър".
Например ако имаме следните 6 правоъгълника:
ÚÄÄÄÄÄÄÄÄÄÏ
ÚÄÄÄёÏ Ó
ÚÄÄÄÄÄÏ Ó Ó ÚÄÄёÄÄÄÄÏ
ѐÄÄÄÄÄÙ Ó ѓÄÄÄÄÄÔ Ó
ÚÄÄÄÄÄÄÄÄÄÄÄÔ ѓÄÄÄÄÄÔ Ó
Ó ÚÄÄÄÏ Ó Ó ѐÄÄÄÄђÄÄÙ
Ó ѐÄÄÄÙ Ó Ó Ó
ѐÄÄÄÄÄÄÄÄÄÄÄÔ ѓÄÄÄÄÄÄÄÄÄÄÙ
ѐÄÄÄÄÙ
тяхното обединение е:
ÚÄÄÄÄÄÄÄÄÄÏ
ÚÄÄÄÙ Ó
ÚÄÄÄÄÄÏ Ó ѐÄÄÄÄÏ
ѐÄÄÄÄÄÙ Ó ÚÄÄÄÄÄÏ Ó
ÚÄÄÄÄÄÄÄÄÄÄÄÙ ѐÄÄÄÄÄÙ Ó
Ó ÚÄÄÙ
Ó Ó
ѐÄÄÄÄÄÄÄÄÄÄÄÏ ÚÄÄÄÄÄÄÄÄÄÄÙ
ѐÄÄÄÄÙ
а дължината на границата им е сумата от дължините на всички отсечки, съста-
вящи горната фигура. Задачата е при дадено число N и целочислените координа-
ти на долния ляв и горния десен ъгъл на N правоъгълника, да се намери техния
"периметър".
Допълнение към условието: Счита се, че ако два правоъгълника имат обща от-
сечка, която е част от страна и на единия и на другия, то тази отчсечка вли-
за в състава на "периметъра". С други думи, в обединението на правоъгълници-
те не влизат само отсечките и частите от отсечки, които са изцяло вътре (но
не и на контура) на някой от правоъгълниците.
Р Е Ш Е Н И Е:
--------------
Задачата може да се раздели на 5 основни етапа:
1. Прочитане на входните данни (информацията за дадените правоъгълници) и
запазване в списъци на всички отсечки, които ги съставят. Правят се два спи-
съка - един за хоризонталните и един за вертикалните отсечки.
2. Разпарчеторване на отсечките. Това означава, че всяка отсечка, която е
пресечена с друга отсечка се разрязва на две нови отсечки през пресечната им
точка. Счита се, че една отсечка пресича друга, ако едната е хоризонтална, а
другата вертикална и те имат обща точка. Ако тази обща точка е край на някоя
от отсечките, съответната отсечка не се разрязва (защото няма как). В резул-
тат от разпарчеторването отсечките се преобразувата така, че всяка от тях да
има за край някоя пресечна точка и да не съдържа в себе си пресечни точки.
3. Премахване на всички еднакви отсечки. Еднакви наричаме всяка двойка от-
сечки, които имат едни и същи начални и крайни координати. Ясно е, че две ед-
накви отсечки лежат една върху друга и едната от тях не принадлежи на лицето.
Затова всички отсечки, еднакви с някоя, се изтриват от списъците.
4. Премахване на всички вътрешни отсечки. Всяка отсечка, която лежи изця-
ло вътре в някой правоъгълник се премахва от списъците на отсечките.
5. Намиране и отпечатване на сумата от дължините на всички отсечки, които
са останали в списъците.
}
USES Objects;
CONST InFileName = 'rects.pas';
OutFileName = '';
MaxRects = 500;
MaxLines = 10000;
TYPE TRectangle = record x1,y1,x2,y2: integer; end;
THorLine = record x1,x2,y:integer; end;
TVerLine = record y1,y2,x:integer; end;
THorLineList = array[1..MaxLines] of THorLine;
TVerLineList = array[1..MaxLines] of TVerLine;
PHorLineList = ^THorLineList;
PVerLineList = ^TVerLineList;
VAR R: array[1..MaxRects] of TRectangle;
N,CountH,CountV: integer;
H: PHorLineList;
V: PVerLineList;
Procedure AddHorLine(xx1,xx2,yy:integer); {Добавя в списъка нова хориз.линия}
Begin
Inc(CountH);
with H^[CountH] do
begin x1:=xx1; x2:=xx2; y:=yy; end;
End;
Procedure AddVerLine(yy1,yy2,xx:integer); {Добавя в списъка нова верт. линия}
Begin
Inc(CountV);
with V^[CountV] do
begin y1:=yy1; y2:=yy2; x:=xx; end;
End;
Procedure ReadData; {Прочита входа като списък от правоъгълниците, }
{хоризонталните и вертикалните отсечки (стените на правоъгълниците)}
Procedure AddRectangle(xx1,yy1,xx2,yy2:integer);
Begin
with R[N] do
begin x1:=xx1; x2:=xx2; y1:=yy1; y2:=yy2; end;
End;
Var F: Text;
x1,y1,x2,y2: integer;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N);
New(H); CountH:=0; New(V); CountV:=0;
for N:= 1 to N do
begin
ReadLn(F,x1,y1,x2,y2);
AddRectangle(x1,y1,x2,y2);
AddHorLine(x1,x2, y1);
AddHorLine(x1,x2, y2);
AddVerLine(y1,y2, x1);
AddVerLine(y1,y2, x2);
end;
Close(F);
End;
Procedure Razparchedosvane; {Разпарчедосва отсечките. Всяка отсечка, която}
{се пресича с някоя друга става на две половинки - тези, които я съставят}
Var IndexH,IndexV: integer;
Begin
IndexH:= 1;
repeat
IndexV:= 1;
repeat
with H^[IndexH] do
with V^[IndexV] do {if the lines intercept}
if (x1<=x)and(x<=x2) and (y1<=y)and(y<=y2) then
begin
if (x<>x1) and (x<>x2) then
begin AddHorLine(x,x2,y); x2:=x; end;
if (y<>y1) and (y<>y2) then
begin AddVerLine(y,y2,x); y2:=y; end;
end;
Inc(IndexV);
until IndexV > CountV;
Inc(IndexH);
until IndexH > CountH;
End;
Procedure RemoveIndenticalLines(H:PHorLineList;var Count:integer);
{Сортира дадените отсечки и при повтаряне на някоя линия я отстранява.
Извиква се 2 пъти - за хоризонталните и за вертикалните отсечки}
Var Swp,Mid: THorLine;
Function Less(A,B:THorLine): boolean; {Функция за сравнение на отсечки}
Begin
if A.y < B.y then Less:=true
else if A.y > B.y then Less:=false
else if A.x1 < B.x1 then Less:=true
else if A.x1 > B.x1 then Less:=false
else if A.x2 < B.x2 then Less:=true
else Less:=false;
End;
Procedure QuickSort(Left,Right:word); {Бързо сортиране на отсечки}
Var I,J: integer;
Begin
I:=Left; J:=Right; Mid:= H^[(Left+Right) div 2];
repeat
while Less(H^[I],Mid) do Inc(I);
while Less(Mid,H^[J]) do Dec(J);
if I <= J then
begin Swp:=H^[I]; H^[I]:=H^[J]; H^[J]:=Swp; Inc(I); Dec(J); end;
until I > J;
if Left < J then QuickSort(Left,J);
if I < Right then QuickSort(I,Right);
End;
Function Equal(A,B:THorLine): boolean; {Връща дали са еднакви две отсечки}
Begin
Equal:= (A.y=B.y) and (A.x1=B.x1) and (A.x2=B.x2);
End;
Procedure RemoveEqual;
Var Index: integer;
Begin
Index:=1;
repeat
if Equal(H^[Index],H^[Index+1]) then
begin
Move(H^[Index+1],H^[Index],(CountH-Index)*SizeOf(THorLine));
Dec(CountH);
end
else Inc(Index);
until Index = CountH;
End;
Begin
QuickSort(1,Count);
RemoveEqual;
End;
Procedure RemoveInternalLines; {Internal means "in whole into the rectangle"}
Function InternalLineH(H:THorLine): boolean;
Var I: integer; {Връща дали хориз.линия H е вътрешна за някой правоъгълник}
Begin
for I:= 1 to N do
with R[I] do
if (y1<H.y)and(H.y<y2) and (H.x1>=x1)and(H.x2<=x2) then
begin InternalLineH:=true; Exit; end;
InternalLineH:=false;
End;
Function InternalLineV(V:TVerLine): boolean;
Var I: integer; {Връща дали верт.линия V е вътрешна за някой правоъгълник}
Begin
for I:= 1 to N do
with R[I] do
if (x1<V.x)and(V.x<x2) and (V.y1>=y1)and(V.y2<=y2) then
begin InternalLineV:=true; Exit; end;
InternalLineV:=false;
End;
Var Index: integer;
Begin
{ Remove all completely inside horizontal lines }
Index:=1;
repeat
if InternalLineH(H^[Index]) then
begin
Move(H^[Index+1],H^[Index],(CountH-Index)*SizeOf(THorLine));
Dec(CountH);
end
else Inc(Index);
until Index > CountH;
{ Remove all completely inside vertical lines }
Index:=1;
repeat
if InternalLineV(V^[Index]) then
begin
Move(V^[Index+1],V^[Index],(CountV-Index)*SizeOf(TVerLine));
Dec(CountV);
end
else Inc(Index);
until Index > CountH;
End;
Procedure CalculateAndPrint; {Отпечатва сумарната дължина на отсечките}
Var Sum: longint;
I: integer;
OutF: Text;
Begin
Sum:=0;
for I:= 1 to CountH do
with H^[I] do
Sum:= Sum + abs(x2-x1);
for I:= 1 to CountV do
with V^[I] do
Sum:= Sum + abs(y2-y1);
Assign(OutF,OutFileName); Rewrite(OutF);
WriteLn(OutF,Sum);
Close(OutF);
End;
BEGIN
ReadData;
Razparchedosvane;
RemoveIndenticalLines(H,CountH);
RemoveIndenticalLines(PHorLineList(V),CountV);
RemoveInternalLines;
CalculateAndPrint;
END.