eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Плитки карти

Плитки карти

Ліміт часу 20 секунд
Ліміт використання пам'яті 256 MiB

Друкування карт — складна задачка. Спочатку потрібно знайти потрібне перетворення, щоб помістити карту сферичної Землі на площині, потім виявляється, що для друку високоякісних карт потрібно використовувати декілька аркушів паперу, тому що на один вони не поміщаються. Щоб подолати цю трудність, видавці карт розбивають карту на декілька прямокутних частин і друкують кожну частину окремо. Саме у цьому процесі ви й приймете участь у цій задачі.

Міжнародна асоціація видавців карт намагається скоротити витрати на друкування карт мінімізуючи кількість окремих аркуші, що використовуються для друкування карт. Навіть зі стандартним розміром аркушів та масштабом карти можна оптимізувати витрати аркушів, підлаштовуючи їхнє розміщення.

У лівій частиеі рисунка показано 14 аркушів, які покривають область. У правій частині показано, як ту ж область можна покрити усього 10 аркушами, не змінюючи орієнтацію області, розмір аркушів та масштаб.

Рисунок: Два різних способи розкласти по аркушам Техас

Ваша задача — допомогти Міжнародній асоціації видавців карт знайти мінімальну кількість аркушів, необхідну для покриття заданої області. Для спрощення область є замкнутим многокутником без самоперетинів.

Зверніть увагу, що усі аркуші повинні бути часинами неперервної решвтки, зі сторонами паралельними горизонталі та вертикалі. Аркуші можуть дотикатись лише своїми сторонами повністю і не можуть бути повернуті. Крім того, хоча усі задані координати є цілочисельними, аркуші можуть бути розміщені у нецілочисельних координатах.

Многокутник може дотикатись сторін аркушів (як у прикладі 2). Проте, для того щоб уникнути проблем з машинним поданням раціональних чисел, можна препускати, що відповідь не зміниться якщо вершина многокутника буде знаходитись зовні аркуша на відстані 10^{-6}.

Вхідні дані

Вхідні дані складаються з одного тесту. У першому рядку теста записані три числа n, x_s та y_s. Кількість вершин многокутника n (3n50), x_s та y_s (1x_s, y_s100) - розміри аркушів, якими потрібно покрити карту. Кожен з наступних n рядків містить два цілих числа x та y (0x10x_s, 0y10y_s), які описують вершину многокутника (у напрямку обходу або за годинниковою, або проти годиникової стрілки).

Вихідні дані

Виведіть мінімальну кількість аркушів, необхідних для покриття многокутника.

Приклад

Вхідні дані #1
12 9 9
1 8
1 16
6 16
9 29
19 31
23 24
30 23
29 18
20 12
22 8
14 0
14 8
Вихідні дані #1
10
Джерело ACM-ICPC World Finals 2013