문제
좌표평면 상에 N개의 점들이 존재한다.
N은 짝수이며, 모든 점의 좌표는 양의 정수이다.
임의의 양의 정수 a에 대하여, 좌표가 (a, y)인 점은 최대 두 개이다.
마찬가지로 임의의 양의 정수 b에 대하여, 좌표가 (x, b)인 점은 최대 두 개이다.
x축 또는 y축에 평행한 선분을 그어 점들을 이을 수 있다.
N/2개의 선분을 그어 모든 점이 정확히 하나의 선분의 끝점에 위치하며, 선분이 서로 교차하지 않게 할 수 있는가?
입력
1번 줄 : N
2 ~ N + 1번 줄 : Xi Yi
- 2 ≤ N ≤ 100 000
- 1 ≤ Xi, Yi ≤ 100 000 ((Xi, Yi)는 i번째 점의 좌표)
출력
조건을 만족하게 선분을 그을 수 없다면 첫 번째 줄에 "NO"를 출력하여라. (쌍따옴표 제외)
이외의 경우, 첫 번째 줄에 "YES"를 출력하여라. (쌍따옴표 제외)
이후 N/2개의 줄에 걸쳐 선분으로 이어진 두 점의 번호를 공백으로 구분하여 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 점 | 2 ≤ N ≤ 20, 임의의 양의 정수 a에 대하여 (x, a) 좌표를 가진 점과 (a, y) 좌표를 가진 점은 둘 다 짝수개이다. |
| #2 | 점 | 2 ≤ N ≤ 40 |
| #3 | 점 | 2 ≤ N ≤ 200 |
| #4 | 점 | 2 ≤ N ≤ 2000 |
| #5 | 점 | 문제의 조건 외에 주어진 제한이 없다. |
예제1
입력
8
26
22
44
48
62
66
84
88
출력
YES
12
34
56
78
(1, 2), (3, 4), (5, 6), (7, 8)번 정점 간에 선분을 이으면 선분이 서로 겹치지 않게 이을 수 있다.
출처
COCI 2020 Contest #5