Informatica Online Judge

  레이저 빔 [1555 / 0613]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 34   Total Tried : 291


The Champion of this Problem (C++) : gs18021 - ms / 541byte
My Best Submission (C++) : N/A

[]

Background

2차원 평면상에 N개의 직사각형 상자들이 있다.

상자의 각 변은 각 좌표축과 평행하다. 이들 상자는 다른 상자와 겹쳐지거나 일치할 수 있으며, 다른 것의 내부에 그려질 수도 있다. 상자의 각 꼭지점은 자연수 좌표를 가진다.



위의 그림의 경우는 8개의 상자들이 그려진 경우이다.

이제 이 2차원 평면에 원점 (0,0)에서 레이저 빔을 발사한다.

이 빔이 상자들과 교차되면, 상자들은 파괴된다.

위의 그림의 경우 2, 5, 6, 7, 8번 상자들은 파괴 된다.

(단지 상자의 꼭지점만을 스쳐 지나가더라도 파괴된다.)

가장 많은 상자를 파괴할 수 있도록 빔을 쏘고자 할 때, 몇 개의 상자들을 파괴할 수 있는지 구하는 프로그램을 작성하시오.

위의 그림의 경우 빔을 어떻게 쏘아도 6개 이상의 상자는 파괴할 수 없으므로 5개가 된다.

Input

첫째 줄에 상자의 개수 N이 주어진다.

둘째 줄부터 N개의 줄에는 상자의 왼쪽 아래 꼭지점의 좌표 xbl, ybl과 오른쪽 위 꼭지점의 좌표 xtr, ytr이 순서대로 빈칸 하나를 사이에 두고 주어진다.

[입력값의 정의역]
1≤N≤10,000
각 죄푯값은 10억 자연수

Output

첫째 줄에 최대로 파괴할 수 있는 상자의 개수를 출력한다.

IO Example

입력
8
1 8 7 11
18 10 20 12
17 1 19 7
12 2 16 3
16 7 19 9
8 4 12 11
7 4 9 6
10 5 11 6

출력
5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]