#1273. USACO 2021 February Contest, Bronze —— Problem 2. Comfortable Cows
-
ID: 1273
Type: Default
1000ms
256MiB
Tried: 2
Accepted: 2
Difficulty: 10
Uploaded By:
meilicode
USACO 2021 February Contest, Bronze —— Problem 2. Comfortable Cows
说明
Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard). Initially, the pasture is empty. Farmer John will add $N\ (1≤N≤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≤x_i,y_i≤1,000)$.A cow is said to be "comfortable" if it is horizontally or vertically adjacent to exactly three other cows. Farmer John is interested in counting the comfortable cows on his farm. For each ii in the range $1\ \cdots\ N$, output the total number of comfortable cows after the $i$th cow is added to the pasture.
Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。
Farmer John 将会逐一地将 $N$ 头奶牛加入到草地上。第 $i$ 头奶牛将会占据方格 $(x_i,y_i)$，不同于所有已经被其他奶牛占据的方格。
一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对 $1\ \cdots\ N$ 中的每一个 $i$，输出第 $i$ 头奶牛加入到草地上之后舒适的奶牛的数量。
输入格式
The first line contains a single integer $N$.Each of the next $N$ lines contains two space-separated integers, indicating the $(x,y)$ coordinates of a cow's cell. It is guaranteed that all these cells are distinct.
输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标 $(x,y)$。输入保证所有方格的坐标是不同的。
输出格式
The $i$th line of output should contain the total number of comfortable cows after the first ii cows are added to the pasture.输出的第 $i$ 行包含前 $i$ 头奶牛加入到草地上之后舒适的奶牛的数量。
样例
8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
0
0
0
1
0
0
1
2