프로그램 명: stfd_rectanglestoo
제한시간: 1 초

Note: This problem is almost identical to the previous problem. The single diれence between the two problems has been marked below.

G.1 Description

A rectangle in the Cartesian plane is speci ed by a pair of coordinates ( x 1 ; y 1 ) and ( x 2 ; y 2 ) indicating its lower-left and upper-right corners, respectively (where x 1 x 2 and y 1 y 2 ). Given a pair of rectangles, A = (( x A 1 ; y A 1 ) ; ( x A 2 ; y A 2 )) and B = (( x B 1 ; y B 1 ) ; ( x B 2 ; y B 2 )), we write A B (i.e., A \precedes" B ), if x A 2 < x B 1 and y A 2 < y B 1 : In this problem, you are given a collection of rectangles located in the two-dimension Euclidean plane. Find the length L of the longest sequence of rectangles ( A 1 ; A 2 ; : : : ; A L ) from this collection such that A 1 A 2 : : : A L : G.2 Input G.3 Output

입력

The input le will contain multiple test cases. Each test case will begin with a line containing a single integer n (where 1 n 100000 ), indicating the number of input rectangles. The next n lines each contain four integers x i 1 y i 1 x i 2 y i 2 (where 1000000 x i 1 x i 2 1000000, 1000000 y i 1 y i 2 1000000, and 1 i n ), indicating the lower left and upper right corners of a rectangle. The end-of- le is denoted by a single line containing the integer 0.

출력

For each input test case, print a single integer indicating the length of the longest chain.

입출력 예

입력
3
1 5 2 8
3 -1 5 4
10 10 20 20

출력

2

입력

2
2 1 4 5
6 5 8 10

출력

1

출처:standford/2009/
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]