파일 업로드

이상적인 캐릭터 숫자

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

게임 개발자 수연이 개발하고 있는 게임 맵은 2차원의 '셀'로 구성되어 있으며, 현재는 비어 있는 상태입니다. (체스판과 비슷합니다.)

 

수연은 하나씩 총 NN (1N1051 \le N \le 10^5)개의 캐릭터를 게임 맵에 차례대로 추가할 것입니다. ii번째 캐릭터는 (xi,yi)(x_i,y_i) 셀에 위치하며, 이 위치는 다른 캐릭터들이 차지하는 셀과 다릅니다. (0xi,yi10000 \le x_i,y_i \le 1000). 

 

한 캐릭터가 정확히 세 개의 다른 캐릭터들과 수평 또는 수직으로 인접해 있을 때 '이상적'이라고 합니다.

수연은 게임 맵에서 이상적인 캐릭터의 수를 세고 싶습니다.

 

1N1 \ldots N 범위에 있는 각 ii에 대해 ii번째 캐릭터가 게임 맵에 추가된 후, 이상적인 캐릭터의 총 개수를 출력하세요.

💻 입력

첫 번째 줄에는 하나의 정수 NN이 포함되어 있습니다. 다음 NN개의 줄 각각에는 두 개의 공백으로 구분된 정수가 포함되며, 캐릭터가 위치한 셀의 (x,y)(x, y) 좌표를 나타냅니다. 좌표는 모두 다르다는 것이 보장됩니다.

🖨️ 출력

ii번째 출력 행은 첫 번째 ii 캐릭터가 게임 맵에 추가된 후, 이상적인 캐릭터의 총 개수를 포함해야 합니다.


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

💡 힌트

처음 네 개의 캐릭터가 추가된 후 (1,1)(1,1)에 있는 캐릭터는 이상적입니다. 

처음 일곱 개의 캐릭터가 추가된 후에는 (2,1)(2,1)에 있는 캐릭터는 이상적입니다.

처음 여덟 개의 캐릭터가 추가된 후에는 (2,1)(2,1)(2,2)(2,2)에 있는 캐릭터는 이상적입니다.

 

점수:

  • 테스트 케이스 1-4는 N400N \le 400을 만족합니다.
  • 테스트 케이스 5-12는 추가적인 제약조건을 만족하지 않습니다.

출처: USACO 2021 February Contest, Bronze Problem 2. Comfortable Cows