P3072 [USACO13FEB] Perimeter S

题目背景

征求翻译。如果你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。

题目描述

农夫约翰已经在他的一片田地中间放置了 $n$ 个干草堆。我们可以认为这片田地是由 $10^6 \times 10^6$ 个小方格组成的矩阵,每个干草堆占据一个小方格(当然,没有两堆干草占据同一个格子)。 FJ 注意到他的干草堆组成了一个大的连通块,这就意味着从任何一个草堆走起,可以通过相邻草堆走若干步到达其他任意的草堆。这个连通块的内部可能包含若干个“洞”——被干草堆完全包围的空白格子。 请帮助FJ计算整个连通块的周长。计算周长时请不要考虑“洞”。

输入格式

第 $1$ 行:干草堆的数量 $n$。 第 $2 \sim n + 1$ 行:每行两个数,表示干草堆的坐标 $(x, y)$。

输出格式

连通块的周长 $p$。

说明/提示

对所有的数据,满足 $1 \leq n \leq 5 \times 10^4$,$1 \leq x, y \leq 10^6$。