7866 - 试题G:圈地养猪 15'

通过次数

214

提交次数

278

时间限制 : 1 秒
内存限制 : 256 MB

由于猪价暴涨,JM准备圈地养猪。

但是猪崽从哪来呢?当然是去抓野山猪咯~

已知每一头野山猪的坐标,现在JM需要用围栏围成一个矩形,在矩形内的猪就都属于JM了。围起来的野山猪当然是越多越好啦,贪心的JM想把所有的野山猪给围起来。但是JM不知道得准备多长的围栏。你能帮JM吗计算一下至少需要多长的围栏,围成的矩形能够把所有的野山猪围起来。

注意:

  1. 围栏的四个角必须在整数坐标点上,而且有野山猪的点是不能够构建围栏的~
  2. 所围矩形的边必须平行于x或者y轴。

输入

第一行输入一个整数n,表示野山猪的头数

接下来n行,每行输入两个整数x\ y,表示野山猪所处的位置(x,y)

输出

输出一个整数,表示需要的围栏长度

样例

输入

4
0 0
1 1 
2 2
3 3

输出

20

输入

5
44 62
34 69
24 78
42 44
64 10

输出

224

输入

4
1 100
1 0
1 -100
1 0

输出

408

提示

样例1解释

15864568013056.png

数据规模

对于50\%的数据,2 \le n \le 100, x = 1

对于100\%的数据,2 \le n \le 10000, -1000000 \le x, y \le 1000000,一个坐标点上可能会有多头野山猪

来源

竞码编程-蓝桥杯模拟赛5(大学生组&青少年组)