#PU1110. USACO 2021 February Contest, Silver — Problem 1. Comfortable Cows

USACO 2021 February Contest, Silver — Problem 1. Comfortable Cows

USACO 2021 February Contest, Silver — Problem 1. Comfortable Cows

题目描述

Farmer Nhoj's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard). Initially, the pasture is empty. Farmer Nhoj will add NN (1≤N≤1051\le N\le 10^5) cows to the pasture one by one. The iith cow will occupy a cell (xi,yi)(x_i,y_i) that is distinct from the cells occupied by all other cows (0≤xi,yi≤10000\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 Nhoj 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 xx and yy coordinates in the range 0…10000 \ldots 1000. For each ii in the range 1…N1 \ldots N, please output the minimum number of cows Farmer Nhoj would need to add until no cows are comfortable if initially, the pasture started with only cows 1…i1\ldots i.

输入格式

The first line contains a single integer NN. Each of the next NN lines contains two space-separated integers, indicating the (x,y)(x,y) coordinates of a cow's cell.

输出格式

The minimum number of cows Farmer Nhoj needs to add for each ii in 1…N1 \ldots N, on NN separate lines.

数据范围

(见题面原文)

样例

样例 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
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)$.
Problem credits: Benjamin Qi