Задачи
Объединение прямоугольников 2
Объединение прямоугольников 2
Объединение прямоугольников куда проще, если их стороны параллельны осям координат. Найдите объединение множества таких прямоугольников.
Входные данные
В первой строке задано количество прямоугольников n (2 ≤ n ≤ 15). На следующих n строках записаны прямоугольники координатами двух противоположных углов в формате x1 y1 x2 y2
. Координаты являются целыми числами и принадлежат промежутку [-109
, 109
].
Допускаются вырожденные прямоугольники.
Выходные данные
Выведите площадь объединения прямоугольников.
Входные данные #1
2 0 0 10 10 20 5 5 20
Выходные данные #1
300
Входные данные #2
2 0 0 10 10 20 15 15 20
Выходные данные #2
125
Входные данные #3
2 0 0 10 10 3 5 5 3
Выходные данные #3
100
Входные данные #4
3 0 0 10 10 13 5 5 13 12 12 15 15
Выходные данные #4
147