题目描述(ID:12375)
标题: 围城
标签: 搜索 搜索与剪枝 记忆化搜索
详情:
编程星球上有一片100*100的空地,啊哈沃德在此处建立了N座发电站,每座发电站占地位置1*1格。
为了防止源码巨人的攻击,啊哈沃德需要在所有发电站外围修建电网,电网需要紧贴着发电站外缘建造,将所有发电站区域围绕进去。不过,由于建筑摆放问题,发电厂区域中可能有部分未被占满的“空洞”,这些空洞在发电站区域的内部,不用建造电网。
请帮啊哈沃德计算需要建造的电网长度是多少?
输入格式:
第一行给出一个正整数N,(1<=N<=10000),表示有N座发电站。
接下来N行每行包含两个正整数x,y,(1<=x,y,<=100),对应每一座发电站的坐标。
输出格式:
一个整数,表示需要建造的电网的长度。
样例:

输入

9
7 3
5 3
5 5
8 4
6 3
3 3
7 4
6 5
5 4

输出

18

解释

根据题意,发电厂的分布如下。可计算出其外围的长度为18,注意其中有1格空洞,但这个空洞在发电站的内部,不用建造电网。
登录并解答