Олимпиадный тренинг

Задача . Разделяй и властвуй


Задача

Темы:
В тридесятом государстве ради сбора мытных денег (таможенных пошлин) с торговых людей царь Салтан указал сделать зáсеки – заградительный полосы, которые тянутся с севера на юг или с запада на восток и преграждают путь всякому пешему и конному.

Тридесятое государство имеет форму прямоугольника, стороны которого тянутся с запада на восток и с севера на юг. Картограф изобразил карту государства в виде прямоугольника на системе координат с центром O, совпадающим с юго-западным углом страны и осями, параллельными осям координат. Засеки на карте изображены в виде отрезков различной длины, параллельных осям координат. При этом оказалось, что никакие два отрезка не пересекаются и не лежат на одной прямой.


Для удобства управления своей страной царь Салтан повелел разделить ее на непересекающиеся прямоугольные области с соблюдением следующих условий: 

1)    каждая засека входит полностью в границы областей
2)    число областей должно быть наименьшим, дабы уменьшить расходы на приказный люд.

Напишите программу, помогающую картографическому приказу построить искомое разбиение.

Входные данные
В первой строке находятся координаты северо-восточного угла страны, Во второй строке указано количество засек N (N≤1000). Каждая из следующих N строк содержит описание одной из засек в виде четверки числе x1, y1, x2, y2, что соответствует отрезку с концевыми точками (x1, y1)  и (x2, y2). Все координаты являются неотрицательными целыми и не превосходят 10000.

Выходные данные
В первую строку  выведите количество областей M в найденном разбиении. В последующих M строках должны находиться целочисленные координаты юго-западного и северо-восточного углов для каждой из областей разбиения. Числа внутри строки разделять пробелами.
 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя