1

Тема: Дошка оголошень

Дошка оголошень: В університеті на стіні висить безліч оголошень. На стіні утворилася дуже багато шарів цієї макулатури, й в кінці кінців вирішили все-таки зняти. Кілька студентів погодилися виконати цю роботу. Вони вирішили укласти парі – хто точніше вгадає, яка площа стіни зараз порожня, яка максимальна кількість наклейних один на одного шарів оголошень, та яка площа стіни покрита максимальною кількістю шарів. Завдання – обчислити ці значення.
Перший рядок вхідних даних містить три цілих числа, відокремлених пропусками – N, W, H (0<N≤1000, 0<W≤50000, 0<H≤40000) – кількість оголошень на стіні, її ширина та висота відповідно. Кожен з наступних N рядків містить чотири цілих числа через пробіл – Ax, Ay, Bx, By (0≤Ax<Bx≤W, 0≤Ay<By≤H) – координати нижнього лівого та правого верхнього кутів оголошення відповідно.
Вивести 3 цілих числа, відокремлених пропусками – площа не покритій оголошеннями стіни, максимальна кількість шарів, і площа стіни, зайнята максимальною кількістю шарів.

2 Востаннє редагувалося /KIT\ (27.07.2021 12:32:33)

Re: Дошка оголошень



3

Re: Дошка оголошень

Нічого

4

Re: Дошка оголошень

з чого почати?

5 Востаннє редагувалося /KIT\ (27.07.2021 12:32:38)

Re: Дошка оголошень



6 Востаннє редагувалося ReAl (19.05.2018 10:18:42)

Re: Дошка оголошень

Красива задачка. «Де мої 20 років», щоб ото хтось задав та посидіти порозв'язувати. Тепер хіба на пенсії.

Почати можна з CLRS, розділ 14. (підрозділ 14.3 Інтервальне дерево).