配点: 7 点
問題文
AtCoder 农园里有 N 根桩, i 本根桩的位置在坐标 (X_i,Y_i) 。
你希望围起所有桩的围墙,并在围墙的周长上以及内部的所有格点上插上桩。
由于建造长围墙很累,所以我们要制作围起所有桩的周长最短的围墙。
请计算你需要新插的桩的数量。
但是,桩的粗细和围墙的厚度可以忽略。
制約
- 3 \leq N \leq 10^5
- 0 \leq X_i,Y_i \leq 10^9\ (1\leq i\leq N)
- i\neq j 如果 (X_i,Y_i)\neq(X_j,Y_j)
- 所有输入均为整数
小课题·得点
这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
每个小任务在满足上述约束之外,还需满足以下约束。
- (2 点): N=3,X_i,Y_i\leq1000
- (2 点): X_i,Y_i\leq1000
- (3 分数):没有额外约束。
入力
输入是按以下格式从标准输入给出的。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
请输出你将要插的桩的数量。
入力例 1
3 1 4 6 1 5 8
出力例 1
17
你将要建造的围栏将如下面的图所示。
此时围栏的周长是 9\sqrt{2}+\sqrt{34}=18.5588\ldots ,比这个短的围栏无法围住所有的桩。

新增加的点 (2,4),(2,5),(3,3),(3,4),(3,5),(3,6),(4,3),(4,4),(4,5),(4,6),(4,7),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7) 对应于 17 将需要打入的桩数,因此答案是 17 。
入力例 2
3 2 2 2 3 3 2
出力例 2
0
1 有些情况下也不需要新打桩。

入力例 3
3 2 39 39 35 17 5
出力例 3
599
如下面的图所示,新增 599 根桩是必要的。

入力例 4
10 72 7 54 25 97 48 37 47 34 54 4 16 62 1 59 22 99 73 34 75
出力例 4
4828
此输入示例是一个小作业。 1 不满足约束,但小任务 2,3 约束。
如下面的图所示,新增 4828 根桩是必要的。

入力例 5
30 878317816 654163251 686185971 65193664 421988001 893301255 337790787 848308131 116633641 453711858 147679897 275450390 871549713 368160131 945135251 515070794 113677189 553747963 648722370 798825746 334960984 163211483 477414168 849868430 46724716 593116536 424597820 84043071 456749260 981436379 167906984 546584517 187306934 201207913 535850448 43428774 602081737 111568378 607467836 80430906 965538187 537789555 69199019 485172741 267885487 934316143 883812229 276272851 507976072 19708905 951100460 639017801 43859603 556279043 300658736 79240016 231304846 220059094 854667690 399502355
出力例 5
607281204170558988
此输入示例是一个小作业。 1,2 不满足约束,但小任务 3 约束。
输出的值是 32 可能超出 bit 整数的范围。