문제
농부 창호의 목초지는 무한한 2차원 격자로 이루어져 있다. 초기 모든 목초지는 비어있다.
농부 창호는 N마리의 소를 순서대로 목초지에 배치시키는데, i번째 소는 (xi,yi) 목초지 위에 놓이게 되며, 모든 소는 서로 다른 곳에 배치된다.
소는 인접한 4개의 목초지 중 3개의 목초지에 소가 있고, 1개의 목초지가 비어있을 경우, 편안하다고 느낀다.
편안한 소는 우유 생산이 느려지기에, 농부 창호는 편안한 소가 존재하지 않도록 하고 싶다.
i번째 소까지 배치되었을 경우, 편안한 소가 없을때까지 추가해야 하는 소의 수를 구하라.
입력
첫 번째 줄에 소의 수 N이 주어진다. N은 1 <= N <= 105 정수이다.
그 다음 N개의 줄에 걸쳐, i번째 소의 좌표 (xi,yi>) 가 각각 공백으로 구분되어 주어진다.
입력되는 좌표는 0 <= (xi,yi) <= 1000 정수이다.
출력
i번째 소까지 배치되었을 경우, 편안한 소가 없도록 추가해야 하는 최소 소의 수를 출력하시오.
예제1
입력
9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 1
출력
0
0
0
1
0
0
1
2
4
4번째 소까지 배치될 경우, (2,1)에 추가로 소를 배치하면 모든 소를 불편하게 만들 수 있다.
9번째 소까지 배치될 경우, (2,0), (3,0), (2,-1), (2,3)에 추가로 소를 배치하면 모든 소를 불편하게 만들 수 있다.
힌트
출처
USACO 2021 February Silver