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

Плитки карты

Плитки карты

Печать карт --- сложная задачка. Сначала нужно найти подходящее преобразование, чтобы уместить карту сферической Земли на плоскости, потом оказывается, что для печати высококачественных карт нужно использовать несколько листов бумаги, потому что на один они не помещаются. Чтобы преодолеть эту трудность, издатели карт разбивают карту на несколько прямоугольных частей и печатают каждую часть отдельно. Именно в этом процессе вы примете участие в этой задаче. Международная ассоциация издателей карт старается сократить расходы на печать карт минимизируя количество отдельных листов, используемых для печати карт. Даже со стандартным размером листов и масштабом карты можно оптимизировать расход листов, подстраивая их расположение. В левой части рисунка показаны\textbf{ 14 }листов, покрывающие область. В правой части показано, как ту же область можно покрыть всего \textbf{10} листами, не изменяя ориентацию области, размер листов и масштаб. \includegraphics{https://static.e-olymp.com/content/cc/cc7804e151a8e6eb8202adf7187241a034d7b703.jpg} \textit{\textbf{Рисунок}}: Два разных способа разложить по листам Техас Ваша задача --- помочь Международной ассоциации издателей карт найти минимальное количество листов, необходимое для покрытия заданной области. Для простоты область является замкнутым многоугольником без самопересечений. Обратите внимание, что все листы должны являться частями непрерывной решетки, со сторонами параллельными горизонтали и вертикали. Листы могут касаться только своими сторонами полностью и не могут быть повернуты. Кроме того, хотя все заданные координаты являются целочисленными, листы могут быть расположены в нецелочисленных координатах. Многоугольник может касаться сторон листов (как в примере \textbf{2}). Однако, для того чтобы избежать проблем с машинным представлением рациональных чисел, можно предполагать, что ответ не изменится если вершина многоугольника будет находиться снаружи листа на расстоянии \textbf{10^\{-6\}}. \InputFile Входные данные состоят из одного теста. В первой строке теста записаны три числа \textbf{n}, \textbf{x_s} и \textbf{y_s}. Количество вершин многоугольника \textbf{n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{50}), \textbf{x_s} и \textbf{y_s} (\textbf{1} ≤ \textbf{x_s}, \textbf{y_s} ≤ \textbf{100}) - размеры листов, которыми нужно покрыть картую. Каждая из следующих \textbf{n} строк содержит два целых числа \textbf{x} и \textbf{y} (\textbf{0} ≤ \textbf{x} ≤ \textbf{10x_s}, \textbf{0} ≤ \textbf{y} ≤ \textbf{10y_s}), описывающих вершину многоугольника (в направлении обхода либо по часовой, либо против часовой стрелки). \OutputFile Выведите минимальное количество листов, необходимых для покрытия многоугольника.
Лимит времени 20 секунд
Лимит использования памяти 256 MiB
Входные данные #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