파일 업로드

무 입자

profile
실행 시간 제한메모리 제한
1 초512 MB
📃 해결할 문제

COVID-19의 유행 동안 격리된 구역에서 과학자들은 지루함을 덜기 위한 새로운 방법을 생각해냈습니다. 그것은 고급 물리학을 공부하기! 실제로, 그들은 새로운 소립자를 발견해냈고, 그것을 "무 입자"라 명명했습니다.

과학자들은 현재 NN (1N1051 \leq N \leq 10^5)개의 무 입자로 실험을 진행 중입니다. 입자 iixix_iyiy_i라는 두 정수로 표현되는 "스핀"을 가지며, 이 두 정수는 109109-10^9 \ldots 10^9 범위 내에 있습니다. 가끔 두 개의 무 입자는 상호작용합니다. 이 상호작용은 스핀이 (xi,yi)(x_i, y_i)인 입자와 (xj,yj)(x_j, y_j)인 입자 사이에서만 발생할 수 있으며, 이때 xixjx_i \leq x_j 그리고 yiyjy_i \leq y_j 조건을 만족해야 합니다. 이러한 조건 하에서, 이 두 입자 중 정확히 하나가 사라질 수 있습니다(다른 입자에는 아무 일도 일어나지 않습니다). 

주어진 시간에 최대 한 번의 상호작용만 일어날 수 있습니다.

과학자들은 임의의 상호작용 순서 후에 남을 수 있는 무 입자의 최소 개수를 알고 싶어합니다.

💻 입력

첫 번째 줄에는 무 입자의 초기 개수인 단일 정수 NN이 들어 있습니다. 

다음 NN 행 각각에는 한 입자의 스핀을 나타내는 두 정수가 공백으로 구분되어 있습니다. 

각 입자는 구별되는 스핀을 가지고 있습니다.

🖨️ 출력

임의의 상호작용 순서 후에 남을 수 있는 무 입자의 최소 개수를 나타내는 단일 정수를 출력하세요.


💻 예제 입력 1
4
1 0
0 1
-1 0
0 -1
🖨️ 예제 출력 1
1
💻 예제 입력 2
3
0 0
1 1
-1 3
🖨️ 예제 출력 2
2

💡 힌트

상호작용이 이루어질 수 있는 한가지 순서:

  • 입자 1과 4가 상호작용하며, 입자 1이 사라집니다.
  • 입자 2와 4가 상호작용하고, 입자 4가 사라집니다.
  • 입자 2와 3이 상호작용하며, 입자 3이 사라집니다.

오직 입자 2만 남습니다.

 

샘플 입력:

3
0 0
1 1
-1 3

샘플 출력:

2

입자 3는 다른 두 입자들과는 상호작용할 수 없으므로 그것은 반드시 남아 있어야 합니다. 입자 1과 2 중 적어도 하나는 남아 있어야합니다.

 

점수:

  • 테스트 케이스 3-6은 N1000.N \leq 1000. 조건을 만족합니다.
  • 테스트 케이스 7-12는 추가 제약조건을 만족하지 않습니다.

출처: USACO 2020 US Open Contest, Silver Problem 3. The Moo Particle