Задача №111646. Флешмоб
Для участников олимпиады на главной площади города «У» планируется игра в форме флешмоба. Главная площадь замощена плитками, образующими клетчатое поле.
Сначала составляется план игры: каждый участник флешмоба получает номер в очереди выхода на площадь и координаты двух различных плиток, находящихся в одном ряду или столбце. После этого на площади раскладываются призы, затем участники выходят на площадь по очереди. Очередной участник забирает все призы, находящиеся в указанных ему клетках, и клетках, находящихся между ними.
Призы должны быть разложены так, чтобы каждому участнику достался по крайней мере один приз.
Требуется написать программу, которая по плану игры находит минимальное необходимое количество призов, и на какие именно плитки их следует разложить.
В первой строке входного файла содержится число N — количество участников флешмоба (1 ≤ N ≤ 123 456). Каждая из последующих N строк содержит четыре целых числа x1i, y1i, x2i, y2i — координаты плиток для i-го участника (1 ≤ x1i, y1i, x2i, y2i ≤ 109; либо x1i = x2i, либо y1i = y2i). Участники перечислены в порядке выхода на площадь.
Первая строка выходного файла должна содержать число M — минимальное количество призов, которые должны быть разложены на площади. Каждая из последующих M строк должна содержать два числа pxi и pyi — координаты плитки, на которой должен лежать i-й приз.
Если вариантов размещения призов, удовлетворяющих условию задачи, несколько, то выведите любой из них. Если решения не существует, выведите единственное число 0.
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.
5 2 1 2 4 2 4 4 4 5 1 1 1 4 4 4 2 4 2 1 2
5 1 2 4 3 1 1 3 4 2 3
3 1 1 1 3 2 1 2 3 1 2 2 2
0
4 1 1 1 3 2 1 2 3 3 3 3 1 1 3 4 3
4 4 3 3 1 2 1 1 1