[Back to MISC SWAG index] [Back to Main SWAG index] [Original]

    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.

[Back to MISC SWAG index] [Back to Main SWAG index] [Original]