問題文

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 点): 追加の制約はない。

入力例 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 整数に収まらない場合もあります。