printРабочее место участника

printЗадачи

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

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На плоскости расположено несколько прямоугольников. Каждый прямоугольник на плоскости задается координатами левого нижнего угла `(X_1,\ Y_1)` и правого верхнего угла `(X_2,\ Y_2)`, при этом стороны прямоугольников параллельны осям координат. При наложении друг на друга прямоугольники образуют фигуры, отдельно расположенный прямоугольник – тоже фигура. Прямоугольники, соприкасающиеся только углами, не образуют фигуру. Если прямоугольники соприкасаются сторонами, то они тоже образуют фигуру. Требуется определить фигуру максимальной площади (в качестве ответа вывести площадь такой фигуры).
В первой строке входного файла содержится количество тестов. В первой строке каждого теста записано количество прямоугольников `N`, далее идут `N` строк с координатами вершин прямоугольников `X_1\ Y_1\ X_2\ Y_2`. Координаты вершин – целые, неотрицательные числа, в диапазоне от 0 до 100 включительно. Количество прямоугольников не больше 25.
Для каждого теста в отдельной строке записывается найденная площадь.

Пример ввода

2
2
15 15 25 25
10 10 20 20
5
1 1 6 2
2 1 3 5
2 4 7 5
6 2 7 5
8 4 10 7

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

175
14
Четвертьфинальные соревнования Чемпионата мира Восточно-сибирского региона, 2009
loading