5323 : B24 - 많은 상자
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$ N $ 개의 상자가 있습니다. $ i $ 번째 상자의 세로 길이는 $ X_i $ 이고 가로 길이는 $ Y_i $ 입니다. 다음 두 조건을 모두 만족할 때 상자 A를 상자 B 안에 넣을 수 있습니다.
- (상자 A의 세로 길이) < (상자 B의 세로 길이)
- (상자 A의 가로 길이) < (상자 B의 가로 길이)
상자를 최대 몇 중으로 겹칠 수 있습니까? 단, 상자를 회전시켜 가로와 세로 길이를 바꾸는 조작은 할 수 없습니다.
[제약 조건]
• $1 \le N \le 100000$
• $1 \le X_i \le 500000$
• $1 \le Y_i \le 500000$
• 입력되는 모든 값은 정수입니다.
- (상자 A의 세로 길이) < (상자 B의 세로 길이)
- (상자 A의 가로 길이) < (상자 B의 가로 길이)
상자를 최대 몇 중으로 겹칠 수 있습니까? 단, 상자를 회전시켜 가로와 세로 길이를 바꾸는 조작은 할 수 없습니다.
[제약 조건]
• $1 \le N \le 100000$
• $1 \le X_i \le 500000$
• $1 \le Y_i \le 500000$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫 번째 줄에 상자 개수 $ N $ 이 주어집니다.
두 번째 줄부터 $ N $ 개의 줄에 걸쳐 상자의 크기 $ X_i, Y_i $ 가 주어집니다.
두 번째 줄부터 $ N $ 개의 줄에 걸쳐 상자의 크기 $ X_i, Y_i $ 가 주어집니다.
출력 설명
최대 몇 중으로 겹칠 수 있는지 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
30 50
10 30
40 10
50 20
40 60
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3