미클의 빔
시간 제한8초메모리 제한512 MB
원점을 지나지 않고 서로 겹치지 않는 최대 2000개의 축에 평행한 직사각형이 주어질 때, 모든 직사각형을 지나는 원점에서의 광선의 최소 개수를 구한다.
문제
미클 소령은 N대의 탱크에게 공격받는 비밀 기지를 지켜야 한다. 미클에게는 미클의 빔이라는 최강의 레이저 소총이 있다. 이 빔에 맞은 물체는 즉시 파괴되고, 이를 막을 방법은 없다. 게다가 빔은 물체를 파괴한 뒤에도 계속 나아간다. 이렇게 강력하고 무서운 무기지만 단점이 하나 있다. 빔은 막대한 에너지를 소모한다. 그래서 발사 횟수는 항상 최소여야 한다.
적 탱크를 모두 파괴하는 데 필요한 최소 발사 횟수를 계산하는 프로그램을 작성하라.
다음과 같이 가정할 수 있다.
- 기지는 원점 (0, 0)에 있다.
- 각 탱크는 x축과 y축에 평행한 변을 가진 직사각형이다.
- 어떤 탱크도 원점에 닿거나 원점을 포함하지 않는다.
- 두 탱크가 같은 점을 공유하지 않는다.
- 빔의 폭은 무시할 수 있다.
- 빔은 닿거나 지나가는 모든 탱크를 파괴한다.
입력
입력은 정수 열로 주어진다.
첫 번째 정수는 N (N ≤ 2,000)이다. 이어지는 N개의 줄에는 각각 탱크의 왼쪽 아래 모서리와 오른쪽 위 모서리의 x, y좌표를 나타내는 네 정수가 주어진다. 모든 좌표의 절댓값은 10,000을 넘지 않는다.
출력
빔의 최소 발사 횟수를 출력한다.