레이팅 미적용농부 뇌즈(Nhoj)의 목초지는 정사각형 "칸"들로 이루어진 큰 2차원 격자(거대한 체스판을 떠올려 보자)로 볼 수 있다. 처음에 목초지는 비어 있다.
농부 뇌즈는 목초지에 소 \(N\)마리(\(1\le N\le 10^5\))를 한 마리씩 추가할 것이다. \(i\)번째 소는 다른 모든 소가 차지한 칸과 다른 칸 \((x_i,y_i)\)(\(0\le x_i,y_i\le 1000\))를 차지한다.
어떤 소가 가로 또는 세로로 정확히 세 마리의 다른 소와 인접해 있으면 그 소는 "편안하다"고 한다. 안타깝게도 너무 편안한 소들은 우유 생산량이 뒤처지는 경향이 있어서, 농부 뇌즈는 (자신이 추가하는 소들을 포함하여) 어떤 소도 편안하지 않게 될 때까지 소를 더 추가하려고 한다. 추가되는 소들의 \(x\), \(y\) 좌표가 반드시 \(0 \ldots 1000\) 범위에 있을 필요는 없음에 유의한다.
\(1 \ldots N\) 범위의 각 \(i\)에 대해, 처음에 목초지에 소 \(1\ldots i\)만 있었다면 어떤 소도 편안하지 않게 될 때까지 농부 뇌즈가 추가해야 하는 소의 최소 마릿수를 출력하시오.
문제 제공: Benjamin Qi
문제 제공: Benjamin Qi
첫째 줄에 정수 \(N\)이 주어진다. 다음 \(N\)개의 줄 각각에는 공백으로 구분된 두 정수가 주어지며, 이는 소가 있는 칸의 \((x,y)\) 좌표를 나타낸다.
\(1 \ldots N\)의 각 \(i\)에 대해 농부 뇌즈가 추가해야 하는 소의 최소 마릿수를 \(N\)개의 줄에 출력한다.
9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 10
0
0
1
0
0
1
2
4For \(i=4\), Farmer Nhoj must add an additional cow at \((2,1)\) to make the cow at
\((1,1)\) uncomfortable.
For \(i=9\), the best Farmer Nhoj can do is place additional cows at \((2,0)\),
\((3,0)\), \((2,-1)\), and \((2,3)\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Silver