Рисование окон
Эндрю разрабатывает портативный почтовый клиент KittenMail для сетей на базе технологии FTN. Этот клиент использует текстовый оконный интерфейс, подобный известным оболочкам в стиле Norton.
Теперь Эндрю хочет адаптировать свой почтовый клиент для новой популярной операционной системы Mycrowslowed Widows Not-Tested 0.4. Это несложно, так как в клиенте мало системно-зависимого кода. Однако подсистема окон основана на модуле, который предоставляет системно-независимый интерфейс к функциям работы с экранным буфером.
Эндрю написал простой код для Mycrowslowed Widows, который отображает содержимое буфера окна на экране. Это оказалось легко, поскольку функции аналогичны тем, что используются в других операционных системах. Но он был поражен, когда запустил клиент! Очистка экрана заняла около секунды! Что же пошло не так?
Эндрю начал разбираться в проблеме. Через несколько минут он выяснил, что любой системный вызов Mycrowslowed Widows, обращающийся к экранному буферу, занимает значительное время — 1/6000 секунды или больше. Это ужасно! Что можно сделать?
После нескольких часов размышлений Эндрю решил улучшить свой код. Теперь он хочет использовать специфическую для Widows функцию, которая позволяет рисовать прямоугольник символов вместо последовательных вызовов для отображения каждого символа по отдельности. Эти вызовы хорошо работают в других операционных системах, но очень медленны в Mycrowslowed Widows. Возникла очевидная задача: процедура, перерисовывающая окно, должна отображать его видимые части, используя минимально возможное количество неперекрывающихся операций.
Ваша задача — написать код для одной видимой части окна. Дана часть прямоугольного окна, напишите программу, которая определяет минимальное количество неперекрывающихся прямоугольников, покрывающих эту часть, и находит оптимальный способ покрытия.
Входные данные
Видимая часть окна задана границей, содержащей только горизонтальные и вертикальные сегменты с целочисленными координатами вершин. Часть не содержит отверстий, и ее граница не пересекается и не касается сама себя. Каждый сегмент имеет длину не менее одного символа.
Первая строка ввода содержит число n вершин на границе видимой части. Следующие n строк содержат координаты вершин в порядке против часовой стрелки (координаты y увеличиваются вниз по экрану).
Горизонтальные и вертикальные сегменты чередуются во входных данных. Последний сегмент проводится между последней и первой вершинами. n не превышает 400, а абсолютные значения координат ограничены 200.
Выходные данные
В первой строке выведите m — минимальное количество прямоугольных областей, покрывающих видимую часть окна.
Следующие m строк должны содержать описание одного прямоугольника каждая. Прямоугольник задается четырьмя числами: минимальный x, минимальный y, максимальный x и максимальный y.
Если существует несколько оптимальных решений, выведите любое из них.