P7411 [USACO21FEB] Comfortable Cows S

Farmer Nhoj’s pasture can be viewed as a huge two-dimensional grid made of square cells (imagine a huge chessboard). Initially, the pasture is empty. Farmer Nhoj will add $N$ cows ($1\le N\le 10^5$) to the pasture one by one. The $i$-th cow will occupy the cell $(x_i,y_i)$, which is different from all cells already occupied by other cows ($0\le x_i,y_i\le 1000$). A cow is called “comfortable” if it has exactly three other cows adjacent to it horizontally or vertically. However, cows that are too comfortable often produce less milk, so Farmer Nhoj wants to add some extra cows until no cow (including the newly added cows) is comfortable. Note that the $x$ and $y$ coordinates of the added cows do not necessarily need to be within the range $0 \ldots 1000$. For each $i$ in $1 \ldots N$, output the minimum number of cows Farmer Nhoj needs to add so that there are no comfortable cows, given that the pasture initially contains cows $1 \ldots i$.

The first line contains an integer $N$. The next $N$ lines each contain two space-separated integers, giving the coordinates $(x,y)$ of a cow.

Output $N$ lines. For each $i$ in $1 \ldots N$, output one line containing the number of cows Farmer Nhoj needs to add.

For $i=4$, Farmer Nhoj needs to add a cow at $(2,1)$ so that the cow at $(1,1)$ is no longer comfortable. For $i=9$, Farmer Nhoj’s best plan is to add cows at $(2,0)$, $(3,0)$, $(2,-1)$, and $(2,3)$. Problem by: Benjamin Qi. Translated by ChatGPT 5