Матч 237, Объединение прямоугольников (BoxUnion)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

На плоскости задано множество прямоугольников. Необходимо найти площадь их объединения. Например, площадь объединения трех прямоугольников, заданных в 4 тесте,

равна 35. Массив rectangles содержит набор строк, каждая из которых имеет формат “Left Bottom Right Top”, где (Left, Bottom) – координаты левого нижнего угла, а (Right, Top) – правого верхнего.

Класс: BoxUnion

Метод: int area(vector<string> rectangles)

Ограничения: массив rectangles содержит от 1 до 3 элементов, все координаты вершин изменяются от 0 до 20000 включительно.

Вход. Массив rectangles, содержащий координаты вершин прямоугольников.

Выход. Площадь объединения прямоугольников.

Пример входа

rectangles

{"200 300 203 304"}

{"0 500 20000 501",

"500 0 501 20000"}

{"4 6 18 24",

"7 2 12 19",

"0 0 100 100"}

{"1 3 5 6",

"3 1 7 5",

"4 4 9 7"}

Пример выхода

12

39999

10000

35

РЕШЕНИЕ

геометрия

Поскольку прямоугольников не более трех, воспользуемся принципом включения – исключения. Если в условии задачи прямоугольников меньше трех, то добавим фиктивные прямоугольники с координатами (0, 0, 0, 0) так, чтобы их стало три. Координаты прямоугольников храним в массиве rec.

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

Каждый прямоугольник представляем в виде массива из четырех чисел (Left Bottom Right Top). Функция _area(rect) находит площадь прямоугольника rect. Функция unite(i, j) объединяет прямоугольники i и j. Результатом объединения является прямоугольник. Если прямоугольник не является правильным (в четверке (Left Bottom Right Top) имеет место неравенство Left > Right или Bottom > Top), то его площадь будет равна нулю. Функция unite3(i, j, k) находит общую часть прямоугольников i, j и k.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

vector<int> temp(4);

vector<vector<int> > rec(3,temp);

int _area(vector<int> rect)

{

if ((rect[2] <= rect[0]) || (rect[3] <= rect[1])) return 0;

return (rect[2] - rect[0]) * (rect[3] - rect[1]);

}

vector<int> unite(vector<int> i, vector<int> j)

{

vector<int> res(4);

res[2] = min(i[2],j[2]);

res[0] = max(i[0],j[0]);

res[3] = min(i[3],j[3]);

res[1] = max(i[1],j[1]);

return res;

}

vector<int> unite3(vector<int> i, vector<int> j, vector<int> k)

{

return unite(unite(i,j),k);

}

class BoxUnion

{

public:

int area(vector<string> rectangles)

{

int i, res;

for(i = 0; i < rectangles.size(); i++)

sscanf(rectangles[i].c_str(),

"%d %d %d %d",&temp[0],&temp[1],&temp[2],&temp[3]),

rec[i] = temp;

res = _area(rec[0]) + _area(rec[1]) + _area(rec[2]);

res = res - _area(unite(rec[0],rec[1])) - _area(unite(rec[1],rec[2])) –

_area(unite(rec[0],rec[2]));

res += _area(unite3(rec[0],rec[1],rec[2]));

return res;

}

};