Contributor: SVETLANA KRYUKOVA
program skyline_problem;
{ Programmed by: Svetlana Kryukova
Programmed on: May 19, 1993
}
{-------------------------------------------------------------------------}
const
MaxR = 20; { maximum number of rectangleSkyline }
MaxSkylineSize = 79; { 4*MaxR - 1, maximum size of the Skyline }
type
skyline = array [1..MaxSkylineSize] of integer;
Rectangle = array [1..3] of integer;
Skylines = array [1..MaxR] of Rectangle;
problem_t = record
Points : Skylines;
size : integer;
end;
solution_t = record
Points : skyline;
size : integer;
end;
{-------------------------------------------------------------------------}
function Base_Case(Buildings: problem_t):boolean;
{ Precondition: Buildings is some problem, such that
Buildings.size >= 0 and Buildings.Points is an
array of buildings presented by the array of their
coordinates in the form (x1 y1 x2 y2 ... xn) }
{ Postcondition: return value Base_Case is true if and only if
Buildings is a base-case problem
(Buildings.size = 1) }
begin
Base_Case := (Buildings.size = 1);
end;
{-------------------------------------------------------------------------}
procedure Find_Base_Case_Solution(var Buildings: problem_t;
var Skyline : solution_t);
{ Precondition: Buildings is a base-case problem, such that
Buildings.size = 1 }
{ Postcondition: Skyline is a correct solution to the problem
Buildings such that
Skyline.Points = Buildings.Points[1] }
var
i : integer;
begin
for i := 1 to 3 do
Skyline.Points[i] := Buildings.Points[1][i];
Skyline.size := 3;
end;
{-------------------------------------------------------------------------}
procedure Split(var Buildings, LeftBuildings, RightBuildings: problem_t);
{ Precondition : Buildings is an array of buildings, presented by
an array of coordinates. Building.size > 1
Postcondition: LeftBuildings and RightBuildings are arrays of
buidings and together they are
some permutation of the array Buildings and
|LeftBuildings.size - RightBuildings.size| <= 1 }
var
i : integer;
begin
LeftBuildings.size := Buildings.size div 2;
RightBuildings.size := Buildings.size - Buildings.size div 2;
{Assertion : |LeftBuildings.size - RightBuildings.size| <= 1 }
for i := 1 to LeftBuildings.size do
LeftBuildings.Points[i] := Buildings.Points[i];
{ Assertion: for all i such that 1 <= i <= LeftBuildings.size
LeftBuildings[i] = Buildings[i] }
for i := LeftBuildings.size + 1 to Buildings.size do
RightBuildings.Points[i - LeftBuildings.size] := Buildings.Points[i];
{ Assertion: for all i such that 1 <= i <= RightBuildings.size
RightBuildings[i] = Buildings[i]+LeftBuildings.size }
end;
{-------------------------------------------------------------------------}
procedure Merge(var LeftSkyline, RightSkyline, Skyline : solution_t);
{ Precondition : LeftSkyline and RightSkyline are two arrays of
coordinates presenting two skyline,
Postcondition: Skyline is a common skyline for two LeftSkyline
and RightSkyline }
var i, { pointSkyline to the first unprocessed abscissa of skyline 1 }
j, { pointSkyline to the first unprocessed abcsissa of skyline 2 }
m: integer;
k : 1..2;
CurHeightLeftSkyline, CurHeightRightSkyline, CurHeight: integer;
begin
i := 1;
j := 1;
Skyline.size := 0;
CurHeightLeftSkyline := 0;
CurHeightRightSkyline := 0;
CurHeight := 0;
k := 1;
while (i <= LeftSkyline.size) and (j <= RightSkyline.size) do
if LeftSkyline.Points[i] < RightSkyline.Points[j] then
begin
if i < LeftSkyline.size then
CurHeightLeftSkyline := LeftSkyline.Points[i+1]
else CurHeightLeftSkyline := 0;
if k = 1 then
if CurHeightLeftSkyline >= CurHeightRightSkyline then
begin
Skyline.Points[Skyline.size+1] := LeftSkyline.Points[i];
Skyline.Points[Skyline.size+2] := CurHeightLeftSkyline;
CurHeight := CurHeightLeftSkyline;
Skyline.size := Skyline.size + 2;
end
else
begin
k := 2;
if CurHeightRightSkyline < CurHeight then
begin
Skyline.Points[Skyline.size+1] :=
LeftSkyline.Points[i];
Skyline.Points[Skyline.size+2] :=
CurHeightRightSkyline;
CurHeight := CurHeightRightSkyline;
Skyline.size := Skyline.size + 2;
end;
end
else if CurHeightLeftSkyline > CurHeight then
begin
Skyline.Points[Skyline.size+1] := LeftSkyline.Points[i];
Skyline.Points[Skyline.size+2] := CurHeightLeftSkyline;
CurHeight := CurHeightLeftSkyline;
k := 1;
Skyline.size := Skyline.size + 2;
end;
i := i + 2;
end { if LeftSkyline.Points[i] < RightSkyline.Points[j] }
else if LeftSkyline.Points[i] > RightSkyline.Points[j] then begin
if j < RightSkyline.size then
CurHeightRightSkyline := RightSkyline.Points[j+1]
else CurHeightRightSkyline := 0;
if k = 2 then
if CurHeightRightSkyline >= CurHeightLeftSkyline then begin
Skyline.Points[Skyline.size+1] :=
RightSkyline.Points[j];
Skyline.Points[Skyline.size+2] :=
CurHeightRightSkyline;
CurHeight := CurHeightRightSkyline;
Skyline.size := Skyline.size + 2;
end else begin
k := 1;
if CurHeightLeftSkyline < CurHeight then begin
Skyline.Points[Skyline.size+1] :=
RightSkyline.Points[j];
Skyline.Points[Skyline.size+2] :=
CurHeightLeftSkyline;
CurHeight := CurHeightLeftSkyline;
Skyline.size := Skyline.size + 2;
end;
end else if CurHeightRightSkyline > CurHeight then begin
Skyline.Points[Skyline.size+1] := RightSkyline.Points[j];
Skyline.Points[Skyline.size+2] := CurHeightRightSkyline;
CurHeight := CurHeightRightSkyline;
k := 2;
Skyline.size := Skyline.size + 2;
end;
j := j + 2;
end { if LeftSkyline.Points[i] > RightSkyline.Points[j] }
else begin
if i < LeftSkyline.size then CurHeightLeftSkyline :=
LeftSkyline.Points[i+1]
else CurHeightLeftSkyline := 0;
if j < RightSkyline.size then
CurHeightRightSkyline := RightSkyline.Points[j+1]
else CurHeightRightSkyline := 0;
if CurHeightLeftSkyline >= CurHeightRightSkyline then begin
k := 1;
if CurHeightLeftSkyline <> CurHeight then begin
Skyline.Points[Skyline.size+1] :=
LeftSkyline.Points[i];
if (i<>LeftSkyline.size) or (j<>RightSkyline.size)
then begin
Skyline.Points[Skyline.size+2] :=
CurHeightLeftSkyline;
Skyline.size := Skyline.size + 1
end;
CurHeight := CurHeightLeftSkyline;
Skyline.size := Skyline.size + 1;
end;
end else begin
k := 2;
if CurHeightRightSkyline <> CurHeight then begin
Skyline.Points[Skyline.size+1] :=
RightSkyline.Points[j];
Skyline.Points[Skyline.size+2] :=
CurHeightRightSkyline;
CurHeight := CurHeightRightSkyline;
Skyline.size := Skyline.size + 2;
end;
end;
i := i + 2;
j := j + 2;
end;
for m := i to LeftSkyline.size do begin
Skyline.Points[Skyline.size+1] := LeftSkyline.Points[m];
Skyline.size := Skyline.size + 1;
end;
for m := j to RightSkyline.size do begin
Skyline.Points[Skyline.size+1] := RightSkyline.Points[m];
Skyline.size := Skyline.size + 1;
end;
end;
{-------------------------------------------------------------------------}
procedure Find_Skyline(var Buildings : problem_t;
var Skyline : solution_t);
var
LeftBuildings, RightBuildings : problem_t;
LeftSkyline, RightSkyline : solution_t;
begin
if Base_Case(Buildings) then
Find_Base_Case_Solution(Buildings, Skyline)
else
begin
Split(Buildings, LeftBuildings, RightBuildings);
Find_Skyline(LeftBuildings, LeftSkyline);
Find_Skyline(RightBuildings, RightSkyline);
Merge(LeftSkyline, RightSkyline, Skyline);
end;
end;
{-------------------------------------------------------------------------}
procedure GetProblem(var Buildings : problem_t);
var
i, j : integer;
begin
write(output, ' Enter the number of buildings in the City: ');
readln(input, Buildings.size);
write(output,
' Enter only three coordinates for each building, x1 y x2, ');
writeln (output, 'representing ');
writeln (output, ' the building (x1,0),(x1,y),(x2,y) & (x2,0)');
writeln (output, ' (LIMITATIONS: x in [0..300], y in [0..170])');
writeln (output);
for i := 1 to Buildings.size do
begin
write(output, ' Enter building#', i:1, ' coordinates: ');
for j := 1 to 3 do
read(input, Buildings.Points[i][j]);
end;
end;
{-------------------------------------------------------------------------}
procedure DisplayProblem (var Buildings: problem_t);
var k : integer;
begin
writeln('==========================================');
writeln(' Problem is a collection of ', Buildings.size:0, ' builings :');
for k := 1 to Buildings.size do
writeln(' Rectangle #', k:0, ' has coordinates : ',
Buildings.Points[k][1]:0, ' ', Buildings.Points[k][2]:0, ' ',
Buildings.Points[k][3]:0);
end;
{-------------------------------------------------------------------------}
procedure DisplaySolution (var Skyline: solution_t);
var k : integer;
begin
writeln('= = = = = = = = = = = = = = = = = = = = = ');
writeln(' Solution is a skyline of size ', Skyline.size:0);
for k := 1 to Skyline.size do
if (k mod 2) = 1 then writeln(' x', ((k - 1)div 2 + 1):0, ' = ',
Skyline.Points[k]:0)
else writeln(' y', ((k-1) div 2 + 1):0, ' = ', Skyline.Points[k]:0);
end;
{-------------------------------------------------------------------------}
procedure SolveOneProblem;
var
Buildings : problem_t;
Skyline : solution_t;
begin
GetProblem(Buildings);
DisplayProblem(Buildings);
Find_Skyline(Buildings, Skyline);
DisplaySolution(Skyline);
end;
{-------------------------------------------------------------------------}
begin
SolveOneProblem;
end.