8330: Perimeter

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:19 通过:12

题目描述

农夫约翰在他的田地中放置了 N 个干草捆。

我们将这个田地视为一个 1,000,000×1,000,000 的方格矩阵,每个方格均为 1×1大小。

每个干草捆分布在其中一个方格内,没有两个干草捆在同一个方格内。

约翰注意到,他所有的干草捆共同组成了一个大的连通区域,这意味着从任何干草捆开始,通过一系列的向东或西或南或北直接移动至相邻干草捆的操作,可以到达任意其他干草捆。

干草捆组成的连通区域中可能包含“洞”----完全被干草捆包围的空区域。

请帮助约翰确定他的干草捆组成的区域的周长。

请注意,洞不会增加周长。

输入格式

第一行包含整数 N

接下来 N 行,每行包含两个整数 x,y,表示其中一个干草捆的坐标为 (x,y)

(1,1)(1,1) 是约翰田地的左下角方格,(1000000,1000000) 是约翰田地的右上角方格。

输出格式

输出干草捆组成的区域的周长。

数据范围

1≤N≤50000,
1≤x,y≤106

输入格式

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

输出格式

14

输入样例 复制


输出样例 复制


数据范围与提示

样例解释

干草捆组成的连通区域的形状如下:

XX

X  XX

XXX

该区域的周长为 14

需注意,该区域内部的洞并不增加区域的周长。