Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В университете на стене висит множество объявлений.
Их накопилось уже очень много, и когда нужно вешать новую стенную газету или объявление,
то ее просто приклеивали поверх остальных. Таким образом на стене образовалась очень много слоев этой макулатуры,
и в конце концов ее решили все-таки снять. Несколько студентов согласились выполнить эту работу.
При этом они решили заключить пари – кто точнее угадает, какая площадь стены сейчас пустая, каково
максимальное количество налепленных
друг на друга слоев объявлений, и какая площадь стены покрыта этим максимальным количеством слоев.
Для того, чтобы определить победителя пари, они очень аккуратно измерили положение всех объявлений,
перед тем, как их снять. Но так как объявлений очень много, то вручную требуемые числа подсчитать сложно.
Ваша задача – вычислить эти значения.
Первая строка ввода содержит три целых числа, разделенных пробелами – `N`, `W`, `H`
(`0\ <\ N\ ≤\ 1000`, `0\ <\ W\ ≤\ 50000`, `0\ <\ H\ ≤\ 40000`) – количество объявлений на стене,
ее ширина и высота соответственно. Каждая из следующих `N` строк содержит
четыре целых числа через пробел – `A_x,\ A_y,\ B_x,\ B_y` (`0\ ≤\ A_x\ <\ B_x\ ≤\ W`, `0\ ≤\ A_y\ <\ B_y\ ≤\ H`) –
координаты нижнего левого и правого верхнего углов объявления соответственно.
Вывести 3 целых числа, разделенных пробелами – площадь не покрытой объявлениями стены,
максимальное количество слоев, и площадь стены, занятая этим максимальным количеством слоев.
Пример ввода 1
3 45 40
10 10 35 20
20 25 40 35
25 5 30 30
Пример вывода 1
1300 2 75
Пример ввода 2
1 20 30
5 5 15 25
Пример вывода 2
400 1 200
Пример ввода 3
2 2000 1000
0 0 1000 1000
1000 0 2000 1000
Пример вывода 3
0 1 2000000
Пример ввода 4
3 10 10
0 0 10 10
0 0 10 10
0 0 10 10