레이팅 미적용COWVID-19 유행 기간 동안 보호를 위해 격리된 농부 존의 소들은 지루함을 달랠 새로운 방법을 생각해 냈다. 바로 고급 물리학을 공부하는 것이다! 실제로 소들은 새로운 아원자 입자를 발견하는 데 성공했고, 이 입자에 "음매 입자"라는 이름을 붙였다.
소들은 현재 \(N\)개의 음매 입자(\(1 \leq N \leq 10^5\))를 이용한 실험을 진행 중이다. 입자 \(i\)는 \(-10^9 \ldots 10^9\) 범위(양 끝 포함)의 두 정수 \(x_i\)와 \(y_i\)로 표현되는 "스핀"을 가진다. 때때로 두 음매 입자가 상호작용한다. 스핀이 \((x_i, y_i)\)와 \((x_j, y_j)\)인 입자들 사이의 상호작용은 \(x_i \leq x_j\)이고 \(y_i \leq y_j\)일 때만 일어날 수 있다. 이 조건에서, 두 입자 중 정확히 하나가 사라질 수 있다(다른 입자에게는 아무 일도 일어나지 않는다). 어느 시점에서든 많아야 하나의 상호작용만 일어난다.
소들은 임의의 상호작용 순서 이후 남을 수 있는 음매 입자의 최소 개수를 알고 싶다.
문제 제공: Dhruv Rohatgi
배점
- 테스트 케이스 3-6은 \(N\le 1000\)을 만족한다.
- 테스트 케이스 7-12는 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 음매 입자의 초기 개수인 정수 \(N\)이 하나 주어진다. 다음 \(N\)개의 줄 각각에 입자 하나의 스핀을 나타내는, 공백으로 구분된 두 정수가 주어진다. 모든 입자의 스핀은 서로 다르다.
임의의 상호작용 순서 이후 남을 수 있는 음매 입자의 최소 개수인 정수 하나를 출력한다.
moop.in · 출력을 쓸 파일 moop.out4
1 0
0 1
-1 0
0 -11One possible sequence of interactions:
- Particles 1 and 4 interact, particle 1 disappears.
- Particles 2 and 4 interact, particle 4 disappears.
- Particles 2 and 3 interact, particle 3 disappears.
Only particle 2 remains.
3
0 0
1 1
-1 32Particle 3 cannot interact with either of the other two particles, so it must
remain. At least one of particles 1 and 2 must also remain.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > US Open > Silver