Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1743. Прямоугольники
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 3B) |
| 27/06/2012 | Лето 2012 - 3 (B) |
| 21/10/2014 | Занятие 8 (C) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
