레이팅 미적용무한한 2차원 좌표 평면 위에 \(N\) (\(2 \leq N \leq 10^5, N\)은 짝수\()\)개의 점 \((x_i,y_i)\) (\(1 \leq x_i, y_i \leq 10^6\))이 있다.
다음 두 종류의 연산을 원하는 만큼 수행할 수 있다.
- 서로 바로 인접한(맨해튼 거리가 \(1\)인) 두 점을 선택하여 두 점 모두 제거한다.
- 임의의 두 점을 선택하여 y좌표를 교환한다. 형식적으로, 점 \((a,b)\)와 \((c,d)\)는 각각 \((a,d)\)와 \((c,b)\)가 된다.
평면 위의 모든 점을 제거하는 것이 가능한지 판별하시오. 두 점이 같은 좌표에 놓이게 될 수도 있는데, 그래도 서로 다른 점으로 취급해야 한다. 또한 같은 좌표에 있는 점들은 엄밀히는 바로 인접한 것이 아니므로 직접 제거할 수 없다.
문제 제공: Alex Pylypenko, Chongtian Ma
채점 방식
- 입력 2: \(T\le 1000\), \(N \le 6\)
- 입력 3-5: \(N\le 100\)
- 입력 6-11: 추가 제약 조건이 없다.
문제 제공: Alex Pylypenko, Chongtian Ma
첫째 줄에 테스트 케이스의 수 \(T\) (\(1 \leq T \leq 5000\))가 주어진다.
각 테스트 케이스의 첫째 줄에 정수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 두 정수 \(x_i\)와 \(y_i\)가 주어진다.
모든 테스트 케이스에 대한 \(N\)의 합은 \(5\cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트 케이스마다 "YES" 또는 "NO"를 한 줄에 출력한다.
4
2
1 1
1 1
4
6 10
7 11
8 1
8 1
6
1 2
1 3
1 4
1 5
10 10
11 10
6
1 1
1 1
1 1
1 1
10 10
11 11NO
YES
YES
NOFor the first test, the only two points are equal, so no swaps will do anything.
Thus, our answer is NO.
In the second test, we can swap the y-coordinates of 6 and 7 with 8 and 8. Then,
we can remove the first two points (horizontal adjacency) and the last two (vertical).
For the third test, no swaps are needed. We can remove the first pair, second, and
third.
In the last test, it can be shown that no matter how we swap the y-coordinates, we
will never be able to remove all the points in adjacent pairs.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Silver