005 - ものさし

もんだい

XY座標上にN個の異なる整数座標P1からPNがある。
A君は点と点を真っ直ぐな線でつないでP1からPNまでつなげたい。
(つなげる場合の順番は問わない。すべての点を通る必要はない。)
ある点と点についてものさしを当てて鉛筆で1回で真っ直ぐな線を引いてつなげる。
長さが足りない場合に2回以上に分けて線を引いてつなげてはならない。

A君の町には10cmの単位の長さでものさしが売られている。
10cmや20cmのものさしを買うことができる。
例えば、30cmのものさしを買うと30cm以下の長さの真っ直ぐな線が引ける。
A君は点をつなぐ目的を達成したいが、できればあまり長いものさしを買いたくはない。
点をつなぐ目的を達成するのにA君が買う最も短いものさしの長さはいくらか？

入力

N
X1 Y1
.
.
.
Xn Yn

Nは点の数。2≤N≤1000=10^3
Xi,Yiはi番目の点Piの座標。0≤Xi,Yi≤1000000000=10^9
i≠jであれば(Xi,Yi)≠(Xj,Yj)
座標の1単位の長さは1cmである。

出力

A君が買う必要のある最も短いものさしの長さを1行で答えよ。
最後に改行を忘れずに。

さんぷる

入力例1

3
0 0
10 10
15 14

出力例1

20

解説

XY座標上に3つの点がある。
P1は(0,0)であり、P2は(10,10)でありP3は(15,14)である。
点を線でつなげてP1からP3まで線をつなげたい。
このときP1からP2までの距離は14.1421⋯cmであり、P2からP3までの距離は6.4031⋯cmである。
よってP1からP2までは20cmのものさしで線を引く必要がある。
P2からP3までも20cmのものさしで線を引けば良い。
よって、20cmのものさしでP1からP3まで線をつなぐことができる。

入力例2

3
0 0
10 10
5 5

出力例2

10

解説

XY座標上に3つの点がある。
P1は(0,0)であり、P2は(10,10)でありP3は(5,5)である。
点をつなげてP1からP3まで線をつなげたい。
P1からP3までの長さは7.0710⋯cmであるので10cmのものさしがあれば線をつなげることができる。
このサンプルの場合、点P2には必ずしも線をつなげる必要は無い。

入力例3

2
0 0
1000000000 1

出力例3

1000000010

解説

double型の精度の誤差には気をつけてください。

入力例4

10
22332 32623
1203 95262
31305 81403
22442 55471
89784 78507
63397 32214
67779 12590
991 97116
79915 80450
6595 94117

出力例4

27790