Описание
На ось Ox плоскости Oxy положили N прямоугольников

Задание
Требуется найти координаты вершин ломаной, огибающей это множество прямоугольников сверху (см. рисунок ниже)




Входные данные
Первая строка входного файла содержит целое число N (1≤N≤100). Далее следуют N строк, в каждой из которых записана тройка вещественных чисел, описывающих очередной из прямоугольников. Первое из них задает абсциссу левого нижнего угла прямоугольника, а остальные два – его длину и высоту

Выходные данные
В первую строку выходного файла выведите количество вершин искомой ломаной. Далее укажите сами вершины в порядке неубывания абсциссы. Каждая вершина задается своими координатами, записанными через пробел в отдельной строке выходного файла. Никакие два звена ломаной не должны лежать на одной прямой.


Например:

BAR.IN
2
0 4 2
2 4 5

BAR.OUT
6
0 0
0 2
2 2
2 5
6 5
6 0





Идеи
Сетка по встречающимся координатам

Комментарии
Рассмотрим абсциссы всех вершин всех прямоугольников и отсортируем их по возрастанию. В результате ось Ox разобьется на отрезки. Очевидно, что ломаная может менять высоту, на которой идут ее горизонтальные звенья, только в концах этих отрезков, а между ними она идет на постоянной высоте. Определим эти высоты. Возьмем для этого середину каждого отрезка и рассмотрим все прямоугольники, ее покрывающие. Нужно выбрать максимальную из их высот

Тем самым, мы получили набор горизонтальных звеньев нашей ломаной. Вертикальные звенья возникают там, где ломаная меняет высоту, на которой она идет


Упражнение
Придумайте решение этой задачи со временем работы O(N log N). Используйте для этого структуру данных, называемую очередью с приоритетами [Ахо 79, п.4.9]



Решение

{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}

Program bar;
Const
  eps=1E-8;
Var
  X,DX,DY:Array[1..100] of Real;
  N:Integer;
  P:Array[1..1000,1..2] of Real;
  PCount:Integer;
 
Procedure Input;
  Var
    F:Text;
    S:String;
    I,J,K,L:Integer;
  Begin
    Assign(F,'bar.in'); ReSet(F); Read(F,N);
    For I:=1 to N do
      Read(F,X[i],Dx[i],Dy[i]);
    Close(F);
  End;
 
Procedure Add(x,y:Real);
  Begin
    Inc(PCount);
    P[PCount][1]:=X; P[PCount][2]:=Y;
  End;
 
Procedure SolveIt;
  Var
    XX,YY:Array[1..1000] of Real;
    XS:Integer;
    I,J,K,L:Integer;
    R,T:Real;
 
  Procedure AXX(x:Real);
    Begin
      Inc(XS); XX[XS]:=x;
    End;
 
  Begin
    XS:=0;
    For I:=1 to N do
    Begin
      AXX(X[i]); AXX(X[i]+dX[i]);
    End;
    For I:=1 to XS-1 do
      For J:=i+1 to XS do
        if XX[i]>XX[j] then
        Begin
          R:=XX[i]; XX[i]:=XX[j]; XX[j]:=R;
        End;
    For I:=XS-1 downto 1 do
      if abs(XX[i]-XX[i+1])then
      Begin
        For j:=i to xs-1 do
          XX[j]:=XX[j+1];
        Dec(XS);
      End;
    PCount:=0; Add(XX[1],0);
    For I:=1 to XS-1 do
    Begin
      R:=0; T:=(XX[i]+XX[i+1])/2;
      For J:=1 to N do
        if (T>X[j]) and (Tthen
          if Rthen
            R:=dY[j];
      Add(XX[i],R); Add(XX[i+1],R);
    End;
    Add(XX[XS],0);
  End;
 
Function E(x,y:Real):Boolean;
  Begin
    E:=abs(x-y)End;
 
Procedure ClearIt;
  Var
    I,J:Integer;
  Begin
    For I:=PCount-1 downto 2 do
    Begin
      if (e(P[i][1],P[i-1][1]) and e(P[i][1],P[i+1][1])) or
         (e(P[i][2],P[i-1][2]) and e(P[i][2],P[i+1][2])) then
      Begin
        For J:=i to PCount-1 do
          P[j]:=P[j+1];
        Dec(PCount);
      End;
    End;
  End;
 
Procedure PrintIt;
  Var
    F:Text;
    I:Integer;
  Begin
    Assign(F,'bar.out'); ReWrite(F);
    Writeln(F,PCount);
    For I:=1 to PCount do
      Writeln(F,P[i][1]:0:10,' ',P[i][2]:0:10,' ');
    Close(F);
  End;
 
Begin
  Input;
  SolveIt;
  ClearIt;
  PrintIt;
End.
 
 

© Особенности национальных задач по информатике