"Прямоугольники"

С.М.Окулов

На плоскости задано N (1ЈNЈ300) прямоугольников со сторонами, параллельными координатным осям (см. рисунок). Координаты вершин прямоугольников – вещественные числа, заданные с точностью до двух знаков после запятой. Написать программу определения площади фигуры, получающейся в результате объединения прямоугольников.

 

Входные данные. В первой строке файла INPUT.TXT записано число N. В следующих N строках записано по четыре числа – координаты левого нижнего и правого верхнего углов прямоугольника.

Выходные данные. В файле OUTPUT.TXT записывается одно число – площадь фигуры с точностью до четырех знаков.

Пример

Входные данные

4
0 0 10.1 5.2
-3 3 5.36 7
1 6 9 15
8 3 20 8

Выходные данные

195.188

Идея решения

Продлим все вертикальные стороны прямоугольников до пересечения с осью X. Этим мы определим на оси X множество интервалов, внутри каждого из которых длина сечения по оси Y будет постоянной (см. рисунок).

Поэтому для нахождения площади достаточно отсортировать точки на оси X, рассмотреть все сечения и добавить к площади <длину интервала>•<длину сечения>. Для поиска длины сечения используем следующий метод. Началу каждого отрезка присвоим значение признака, равное 1, а его концу –1 и отсортируем точки по значению координаты Y. Подсчитаем сумму значений признаков. Если она не равна нулю, то соответствующий интервал “плюсуем” к длине сечения.

Структуры данных

Const InputFile='Input.TxT';
OutputFile='Output.TxT';
MaxN=300;
Eps=1e-5;
Tochn=4;
Type TPoint=Record X,Y:Real;End;
MasPnt=Array[1..MaxN] Of TPoint;
BMasPnt=Array[1..MaxN*2] Of Real;
BMasSSt=Array[1..MaxN*2] Of LongInt;
Var PrM: Array[1..2] Of MasPnt;
N: LongInt;
Res: Real;
Ox, Oy: BMasPnt;
FOy: BMasSSt;

Процедура инициализации и ввода данных

Координаты вершин прямоугольников храним в массиве PrM, причем в PrM[1] (это массив) – координаты первой вершины, а в PrM[2] – второй. Вершина прямоугольника с меньшими значениями (X, Y) записывается в PrM[1]. Кроме того, значения X запоминаются в массиве Ox.

Procedure ReadPoint(Var A: TPoint);
Begin
Read(A.X, A.Y);
End;

Procedure More(Const a, b: Real): Boolean;
Begin
More:=a-b>Eps;
End;

Procedure Swap(Var a, b: Real);
Var t: Real;
Begin
  t:=a; a:=b; b:=t;
End;

Процедура вывода результата и основная программа очевидны.

Procedure Done;
Begin
  Assign(Output, OutputFile);
  Rewrite(Output);
  WriteLn(Res:0:Tochn);
  Close(Output);
End;

Вспомогательные процедуры

Function Eq(Const a, b: Real): Boolean;
  Begin
    Eq:=Abs(a-b)<Eps;
  End;

Для решения задачи потребуется сортировка элементов массива. Используем метод Хоара.

Sort(Var Ox:BMasPnt; Const lf,rg:LongInt);
Var i,j:LongInt;
x:Real;
Begin
  i:=lf;j:=rg;x:=Ox[(lf+rg) Div 2];
  Repeat
  While More(x, Ox[i]) Do Inc(i);
  While More(Ox[j], x) Do Dec(j);
  If i<=j Then
    Begin
      Swap(Ox[i], Ox[j]);Inc(i); Dec(j);
    End;
  Until i>j;
  If lf<j Then Sort(Ox, lf, j);
  If i<rg Then Sort(Ox, i, rg);
End;

Та же самая сортировка, но с одновременной перестановкой элементов другого массива.

Procedure FstSort(Var Ox: BMasPnt;
Var SOx: BMasSSt;
Const lf, rg: LongInt);
Var i, j: LongInt;
x: Real;
  Begin
   i:=lf;j:=rg;x:=Ox[(lf+rg) Div 2];
   Repeat
    While More(x, Ox[i]) Do Inc(i);
    While More(Ox[j], x) Do Dec(j);
    If i<=j Then
      Begin
       Swap(Ox[i],Ox[j]);
       SwapInt(SOx[i],SOx[j]);
       Inc(i);Dec(j);
      End;
   Until i>j;
   If lf<j Then FstSort(Ox, Sox, lf, j);
   If i<rg Then FstSort(Ox, Sox, i, rg);
End;

Перейдем к основной процедуре – вычислению площади объединения прямоугольников.

Procedure Solve;
Var i: LongInt; m: Real;
Begin
   Sort(Ox, 1, N*2);{сортируем по неубыванию
                    значения координаты X прямоугольников}
   m:=0;Res:=0;{m – длина сечения, Res –
                значение площади объединения прямоугольников}
   For i:=1 To N*2 Do Begin
    If i<>1 Then Res:=Res+Abs((Ox[i]-Ox[i-1])*m);
     {прибавляем площадь очередного сечения}
    If (i=1) Or Not(Eq(Ox[i], Ox[i-1]))
           Then Change(Ox[i], m);
          {определяем новое значение длины сечения}
   End;
End;

Продолжим уточнение.

Function Peres(Const k: LongInt;
Const x: Real): Boolean;
Begin
  Peres:=Not More(PrM[1,k].X,x) And
  More(PrM[2,k].X,x);
End;

И, наконец, последнее уточнение: функция вычисления длины сечения. Для примера на рисунке длина сечения будет равна 10.

Function Calc(Const Ox: BMasPnt;
Const SOx: BMasSSt;
Const N: LongInt): Real;
Var sc: Real;
i, bb: LongInt;
Begin
   sc:=0;bb:=0;
   If SOx[1]>0 Then Inc(bb);
   For i:=2 To N Do Begin
      If bb>0 Then sc:=sc + Ox[i] - Ox[i-1];
      Inc(bb, SOx[i]);
      {изменяем значение признака пересечения интервалов,
       например, для значения 8 на рисунке оно будет
       равно нулю и длина от 8 до 10 не войдет в результат}
  End;
Calc:=sc;
End;