문제
정올사에서 새로 개발한 집적회로는 몇 개의 직사각형 칩들이 겹쳐져서 이루어져 있다.
이제 전선을 연결해야 하는데, 디자인 구조상 두 가닥의 전선을 가로 방향으로 놓는 수밖에 없다.
전선은 직사각형의 변을 지나가기만 해도 그 칩과 연결된다. 그림 A에서 전선은 4개의 칩을 지나가고, 그림 B에선 5개의 칩을 지나간다.
집적회로에 놓인 칩들의 위치가 주어졌을 때,
두 가닥의 전선을 놓아 연결할 수 있는 칩 수의 최댓값을 구하는 프로그램을 작성하라.
입력
첫 줄에 칩의 개수 N이 주어진다.(3<=N<=100,000)
다음 N줄에 걸쳐, 각 칩의 왼쪽 위 모서리의 좌표 X1 Y1과 오른쪽 아래 모서리의 좌표인 X2 Y2가 주어진다.
입력형식은 X1 Y1 X2 Y2의 형식이다. 모든 좌표값은 -107이상 107이하이며, X1 < X2, Y1 > Y2를 항상 만족한다.
출력
두 가닥의 전선으로 연결할 수 있는 칩 수의 최댓값을 출력한다.
예제 #1
5
0 13 4 4
2 14 11 9
7 17 12 12
3 5 16 0
5 2 13 1
5
예제 #2
5
0 4 4 0
1 3 3 1
5 8 9 4
0 12 4 8
1 11 3 9
4
출처
ACM-ICPC Regional Seoul 2018, Problem A
로그인해야 코드를 작성할 수 있어요.