| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 25 | 8 | 4 | 40.000% |
Для участников олимпиады на главной площади города <<У>> планируется игра в форме флешмоба. Главная площадь замощена плитками, образующими клетчатое поле.
Сначала составляется план игры: каждый участник флешмоба получает номер в очереди выхода на площадь и координаты двух различных плиток, находящихся в одном ряду или столбце. После этого на площади раскладываются призы, затем участники выходят на площадь по очереди. Очередной участник забирает все призы, находящиеся в указанных ему клетках, и клетках, находящихся между ними.
Призы должны быть разложены так, чтобы каждому участнику достался по крайней мере один приз.
Требуется написать программу, которая по плану игры находит минимальное необходимое количество призов, и на какие именно плитки их следует разложить.
В первой строке входного файла содержится число $N$ --- количество участников флешмоба (\mbox{1ドル \le N \le 123,456円$}). Каждая из последующих $N$ строк содержит четыре целых числа $x_{1i},ドル $y_{1i},ドル $x_{2i},ドル $y_{2i}$ --- координаты плиток для $i$-го участника (1ドル \le x_{1i},,円 y_{1i},,円 x_{2i},,円 y_{2i} \le 10^9$; либо $x_{1i}=x_{2i},ドル либо $y_{1i}=y_{2i}$). Участники перечислены в порядке выхода на площадь.
Первая строка выходного файла должна содержать число $M$ --- минимальное количество призов, которые должны быть разложены на площади. Каждая из последующих $M$ строк должна содержать два числа $px_i$ и $py_i$ --- координаты плитки, на которой должен лежать $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