农夫约翰在他的田地中放置了 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。
需注意,该区域内部的洞并不增加区域的周长。