직선 두 개

여러 층으로 이루어진 하나의 칩에 CPU, ROM, RAM 같은 전자 회로를 인쇄하려고 한다. 설계상의 제약 때문에 수평 선분인 전선은 두 개만 놓을 수 있다. 전기 신호가 회로를 통과하도록, 두 수평 전선이 가능한 한 많은 회로를 연결하도록 두 전선을 찾아야 한다.

이 문제를 형식적으로 서술하면 다음과 같다. 평면에 축에 평행한 직사각형 n개가 있다. 각 직사각형은 칩에 인쇄할 회로 하나를 나타낸다. 직사각형들은 서로 겹칠 수 있다. 두 수평 직선이 지나가며 만나는 직사각형의 총 개수가 최대가 되도록 두 직선을 찾아야 한다. 수평 직선이 직사각형을 만난다는 것은 그 직선이 직사각형의 윗변 또는 아랫변을 지나는 경우를 말한다. 직사각형이 두 직선 모두와 만나면 총 개수에는 한 번만 센다.

예를 들어 Figure A.1에 있는 직사각형 5개를 보자. Figure A.1(c)의 두 수평 직선(빨간 점선)은 5개 직사각형 모두와 만나고, Figure A.1(b)의 두 수평 직선(빨간 점선)은 4개 직사각형과 만난다.

Figure A.1: (a) 축에 평행한 직사각형 5개. (b) 4개 직사각형과 만나는 두 수평 직선. (c) 5개 직사각형과 만나는 두 수평 직선.

축에 평행한 직사각형의 집합이 주어질 때, 두 수평 직선이 만나는 직사각형의 총 개수가 최대가 되도록 두 직선을 찾는 프로그램을 작성하시오.

프로그램은 표준 입력에서 입력을 읽는다. 첫째 줄에는 평면에 있는 축에 평행한 직사각형의 개수를 나타내는 양의 정수 n이 주어지며, 3 ≤ n ≤ 100,000이다. 이어서 n개의 줄이 주어지고, 각 줄에는 축에 평행한 직사각형의 왼쪽 위 모서리 좌표 (ux, uy)와 오른쪽 아래 모서리 좌표 (vx, vy)를 나타내는 네 정수 ux, uy, vx, vy가 주어지며, ux < vx이고 uy > vy이며, −10,000,000 ≤ ux, uy, vx, vy ≤ 10,000,000이다.

프로그램은 표준 출력에 출력을 쓴다. 정확히 한 줄을 출력한다. 이 줄에는 두 수평 직선이 만날 수 있는 직사각형 개수의 최댓값을 출력한다.