Малювання вікон
Ендрю розробляє портативний поштовий клієнт KittenMail для мережі FTN. Цей клієнт використовує текстовий інтерфейс з вікнами, подібний до відомих оболонок у стилі Нортона.
Тепер Ендрю планує створити версію свого поштового клієнта для нової популярної операційної системи 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.
Якщо існує кілька оптимальних рішень, виведіть будь-яке з них.