もんだい
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