Comfortable Cows

题目描述

Farmer Nhoj 的牧场可以看作一个由正方形“格子”组成的巨大二维网格（可以想象成一个巨大的棋盘）。起初，牧场是空的。 Farmer Nhoj 将依次向牧场中添加 $N$（$1\le N\le 10^5$）头奶牛。第 $i$ 头奶牛将占据一个格子 $(x_i,y_i)$，且该格子与所有其他奶牛所占据的格子都不同（$0\le x_i,y_i\le 1000$）。 如果一头奶牛在水平或垂直方向上恰好与三头其他奶牛相邻，则称其为“舒适（comfortable）”。不幸的是，过于舒适的奶牛往往会降低产奶量，因此 Farmer Nhoj 想要继续添加额外的奶牛，直到没有任何奶牛（包括他额外添加的奶牛）是舒适的。注意，额外添加的奶牛不一定需要满足 $x$ 和 $y$ 坐标在 $0 \ldots 1000$ 的范围内。 对于每个 $i$（$1 \ldots N$），请输出在牧场最初只包含奶牛 $1\ldots i$ 的情况下，为了使没有奶牛是舒适的，Farmer Nhoj 需要添加的奶牛的最小数量。

输入格式

第一行包含一个整数 $N$。 接下来的 $N$ 行中，每行包含两个用空格分隔的整数，表示一头奶牛所在格子的 $(x,y)$ 坐标。

输出格式

对于每个 $i$（$1 \ldots N$），输出 Farmer Nhoj 需要添加的奶牛的最小数量，每个结果占一行，共 $N$ 行。

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

提示

对于 $i=4$，Farmer Nhoj 必须在 $(2,1)$ 处额外添加一头奶牛，使得位于 $(1,1)$ 的奶牛变得不舒适。 对于 $i=9$，Farmer Nhoj 能做到的最优方案是在 $(2,0)$、$(3,0)$、$(2,-1)$ 和 $(2,3)$ 处放置额外的奶牛。 题目鸣谢：Benjamin Qi

标签: USACO|2021|Silver

来源

USACO|2021|Silver