← 返回题目列表

AtCoder · typical90_ao

041. AtCoder农场的堆(★7)

中文机器翻译题面 查看原题

配点: 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)
  • 所有输入均为整数

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
每个小任务在满足上述约束之外,还需满足以下约束。

  1. (2 点): N=3,X_i,Y_i\leq1000
  2. (2 点): X_i,Y_i\leq1000
  3. (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 整数的范围。