#3571. [USACO13OPEN] Perimeter G
[USACO13OPEN] Perimeter G
题目描述
农夫约翰在他的田地中央摆放了N个干草捆(1 ≤ N ≤ 10,000)。田地可以被视为一个100×100的网格,每个干草捆占据其中一个1×1的单元格(显然没有两个干草捆会占据同一个单元格)。
约翰注意到这些干草捆形成了一个大的连通区域,这意味着从任何一个干草捆出发,都可以通过向北、南、东或西移动到相邻的干草捆来到达任何其他干草捆。不过,这个干草捆连通区域中可能存在"空洞"——即被干草捆完全包围的空区域。
请帮助约翰计算这些干草捆形成的区域的周长。注意空洞区域不会对周长产生贡献。
输入格式
第一行包含一个整数N,表示干草捆的数量。
接下来的N行,每行包含两个整数x和y,表示一个干草捆的位置坐标(1 ≤ x, y ≤ 100)。坐标(1,1)表示田地左下角的单元格,(100,100)表示右上角的单元格。
输出格式
输出一个整数,表示干草捆连通区域的周长。
输入输出样例
输入 #1
8
5 3
5 4
8 4
5 5
6 3
7 3
7 4
6 5
输出 #1
14
样例解释
输入的8个干草捆形成的连通区域如下所示(X代表干草捆,空格代表空地):
XX
X XX
XXX
该连通区域的周长为14。例如,区域左侧贡献了3个单位的周长。注意中间的空洞不会对周长产生影响。