문제
직교 좌표 상에서 직사각형은 두 좌표의 쌍으로 나타낼 수 있다. 이 문제에서는 왼쪽 하단 좌표 (X1, Y1)와 오른쪽 상단 좌표(X2, Y2) 로 직사각형을 나타낸다고 하자. 이때 X1≤X2 이고 Y1≤Y2 이다.
두 개의 직사각형 좌표가 A = ((X1, Y1), (X2, Y2)), B = ((X3, Y3), (X4, Y4)) 일 때, X2 < X3 이고 Y2 < Y3 라면 "A는 B에 앞선다." 라고 하고 A ≪ B 로 나타낸다.
N ( 1≤N≤1,000) 개의 사각형이 주어질 때 이 사각형들로 만들 수 있는 부분 집합 중에서 A1 ≪ A2 ≪ ... ≪ AL 을 만족하는 가장 긴 길이의 L을 찾는 프로그램을 작성하시오. 부분 집합의 사각형들은 원래의 순서가 바뀔 수 있다.
입력
입력은 여러 개의 테스트 케이스(5개 이하)로 이루어진다. 입력의 끝은 0 이다. 각 테스트 케이스의 첫 행에는 N( 2≤N≤1,000 ) 이 주어진다. 다음 N 개의 행에는 직사각형의 왼쪽 하단 좌표와 오른쪽 상단좌표를 나타내는 4개의 정수 sXi, sYi, eXi, eYi 가 공백으로 구분되어 주어진다( -1,000,000≤sXi≤eXi≤1,000,000, -1,000,000≤sYi≤eYi≤1,000,000 이고 1≤i≤N).
입력의 끝은 0 이다.
출력
각각의 테스트 케이스에 대하여 가장 긴 길이의 L을 행으로 구분하여 출력하시오.
예제
3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0
2
1
로그인해야 코드를 작성할 수 있어요.