선분 잇기 서브태스크 3초 512MB
문제
2차원 평면 상에 N(N은 짝수)개의 점들이 주어진다.
모든 점들에 대하여 같은 x좌표를 갖는 점들은 최대 2개이며, 같은 y좌표를 갖는 점들은 최대 2개이다.
N/2개의 수직, 수평 선분들을 이용하여 점들을 2개씩 이어주었을 때 어떠한 두 선분도 겹치지 않게 할 수 있는가?
입력
짝수인 정수 N (2 ≤ N ≤ 100 000) 이 주어진다.
이후 N개의 줄에 각 점의 좌표를 의미하는 정수 Xi, Yi (1 ≤ Xi, Yi ≤ 100 000) 가 주어진다. 어떠한 두 점도 겹치지 않음이 보장된다.
출력
조건을 만족하는 선분들을 만들 수 없다면 "NE"를 출력한다. (큰따옴표 제외)
조건을 만족하는 선분들을 만들 수 있다면 "DA"를 출력한다. (큰따옴표 제외)
다음 N/2개 줄에는 공백으로 구분하여 선분으로 연결할 두 점의 번호 i, j를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | 2 ≤ N ≤ 20, 모든 정수 a에 대하여 (a, x) 의 형태의 점들과 (x, a) 형태의 점들은 짝수개임이 보장된다. |
| #2 | 6점 | 2 ≤ N ≤ 20 |
| #3 | 7점 | 2 ≤ N ≤ 40 |
| #4 | 32점 | 2 ≤ N ≤ 2000 |
| #5 | 50점 | 추가 제한조건 없음 |
예제 #1
8
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4
DA
1 5
3 7
2 6
4 8
예제 #2
6
1 2
1 3
2 1
2 4
3 2
3 3
DA
1 2
3 4
5 6
예제 #3
2
1 1
2 2
NE
로그인해야 코드를 작성할 수 있어요.