소 장애물 경주

시간 제한1초메모리 제한128 MB

요약

N개의 축에 평행한 선분 중에서 서로 어떤 점도 공유하지 않도록 최대 개수를 고른다.

난이도: 보통10점 중 7점
유형: 그래프, 유니온 파인드, 기하, 그리디
정답자: 아직 제출이 없습니다

문제

농부 존(FJ)은 다음 인기 관람 스포츠로 소 장애물 경주(Cow Steeplechase)라는 기발한 아이디어를 떠올렸습니다! 잘 알려진 대로, 일반적인 장애물 경주(steeplechase)는 여러 마리의 말이 뛰어넘어야 하는 장애물로 가득한 코스를 도는 경기입니다. FJ는 장애물을 충분히 낮게 만들기만 하면 잘 훈련된 소로도 같은 경기를 할 수 있다고 생각합니다.

코스를 설계하기 위해 FJ는 설치할 수 있는 모든 장애물 후보 $N$ 개( $1 \le N \le 250$ )를 그림으로 그립니다. 각 장애물은 2차원 평면 위에서 가로축 또는 세로축에 평행한 하나의 선분으로 표현됩니다. 장애물 $i$ 는 서로 다른 두 끝점 $(X1_i, Y1_i)$ 와 $(X2_i, Y2_i)$ 를 가지며, $1 \le X1_i, Y1_i, X2_i, Y2_i \le 10^9$ 입니다. 예시 배치는 다음과 같습니다.

   --+-------   
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |

FJ는 어떤 두 장애물도 서로 교차하지 않는다는 조건 아래에서 가능한 한 많은 장애물을 설치하려고 합니다. 위 그림에서 시작하면 FJ는 7개의 장애물을 설치할 수 있습니다.

   ----------   
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |

두 선분은 단 한 점이라도 공유하면 교차하는 것으로 간주하며, 그 점이 한쪽 또는 양쪽 선분의 끝점이어도 마찬가지입니다. 입력에서 어떤 두 수평 선분도 서로 교차하지 않고, 마찬가지로 어떤 두 수직 선분도 서로 교차하지 않는다고 가정해도 됩니다.

FJ가 설치할 수 있는 장애물의 최대 개수를 구하세요.

입력

첫째 줄: 정수 $N$ 하나.
둘째 줄부터 $N+1$ 째 줄까지: $i+1$ 째 줄에는 장애물 $i$ 를 나타내는 네 정수 $X1_i$ , $Y1_i$ , $X2_i$ , $Y2_i$ 가 공백으로 구분되어 주어집니다.

출력

첫째 줄: FJ가 선택할 수 있는, 서로 교차하지 않는 선분의 최대 개수.

힌트

예시에는 세 개의 장애물 후보가 있습니다. $(4, 5)$ 에서 $(10, 5)$ 까지의 수평 선분 하나와, $(6, 2)$ 에서 $(6, 12)$ 까지, 그리고 $(8, 3)$ 에서 $(8, 5)$ 까지의 수직 선분 두 개입니다. 수평 선분이 두 수직 선분 모두와 교차하므로 최대 두 개의 장애물만 설치할 수 있습니다. 서로 교차하지 않는 두 수직 선분을 선택하면 최적해인 2를 얻습니다.

예제1

예제 1
입력
```
3
4 5 10 5
6 2 6 12
8 3 8 5
```
예상 출력
```
2
```