A22494.周长

普及/提高-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

农夫约翰已经在他的一片田地中间放置了n1<=n<=50000n(1<=n<=50000) 个干草堆。我们可以认为这片田地是由100000010000001000000*1000000 个小方格组成的矩阵,每个干草堆占据一个小方格(当然,没有两堆干草占据同一个格子)

FJ 注意到他的干草堆组成了一个大的连通块,这就意味着从任何一个草堆走起,可以通过相邻草堆走若干步到达其他任意的草堆。这个连通块的内部可能包含若干个“洞”——被干草堆完全包围的空白格子。

请帮助FJ计算整个连通块的周长。计算周长时请不要考虑“洞”。

输入格式

第一行:干草堆的数量 nn

2 n+12~n+1 行:每行两个数,表示干草堆的坐标xy(x,y),满足 1<=x,y<=10000001<=x,y<=1000000

输出格式

连通块的周长 pp

输入输出样例

  • 输入#1

    8 
    10005 200003 
    10005 200004 
    10008 200004 
    10005 200005 
    10006 200003 
    10007 200003 
    10007 200004 
    10006 200005 
    

    输出#1

    14 
    

说明/提示

由干草包组成的连接区域如下所示:

XX
X XX
XXX

连接区域的周长长度为 1414(例如,该区域的左侧占此总数的长度为 33 )。请注意,中间的孔对这个数字没有贡献。

首页