Problem 3: Cow Steeplechase [Brian Dean]
Фермер Джон хочет провести коровьий стипль-чез (бег по кругу с препятствиями).
ФД сделал диаграмму всех N (1 <= N <= 250) препятствий, которые он может построить. Каждое препятствие представляет собой горизонтальный или вертикальный отрезок на 2D-плоскости (соответственно, параллельный горизонтальной или вертикальной оси).
Препятствие i имеет различные конечные точки (X1i, Y1i) и (X2i,Y2i) (1 <= X1i, Y1i, X2i, Y2i <= 1,000,000,000).
Например такие:
--+------- -----+----- ---+--- | | | | --+-----+--+- | | | | | | | --+--+--+-+- | | | | |
ФД хочет построить как можно больше таких препятствий при условии, что никакие два из них не пересекаются.
Для диаграммы приведенной выше, ответ – 7.
---------- ----------- ------- | | | | | | | | | | | | | | | | | | |
Для заданной диаграммы определите максимальное количество препятствий, которое может быть построено.
PROBLEM NAME: steeple
Формат входных данных
* Строка 1: Одно целое число: N.
* Строки 2..N+1: Строка i+1 содержит 4 разделенных пробелом целых числа, представляющих препятствие: X1i, Y1i, X2i, and Y2i.
Формат выходных данных
* Строка 1: Максимальное количество не пересекающихся отрезков
Примечание
Оптимальное решение – взять два вертикальных отрезка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 5 10 5
6 2 6 12
8 3 8 5
|
2
|