2072: [USACO 2021 February Contest, Silver] Problem 1. Comfortable Cows
题目描述
Farmer John will add $N$ ($1\le N\le 10^5$) cows to the pasture one by one. The $i$th cow will occupy a cell $(x_i,y_i)$ that is distinct from the cells occupied by all other cows ($0\le x_i,y_i\le 1000$).
A cow is said to be "comfortable" if it is horizontally or vertically adjacent to exactly three other cows. Unfortunately, cows that are too comfortable tend to lag in their milk production, so Farmer John wants to add additional cows until no cow (including the ones that he adds) is comfortable. Note that the added cows do not necessarily need to have $x$ and $y$ coordinates in the range $0 \ldots 1000$.
For each $i$ in the range $1 \ldots N$, please output the minimum number of cows Farmer John would need to add until no cows are comfortable if initially, the pasture started with only cows $1\ldots i$.
输入
输出
样例输入
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提示
For $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)$.