No.168 ものさし

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 117
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

3 ProblemId : 296 / 出題時の順位表

問題文

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

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

入力

$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

$N$は点の数。$2\le N \le 1000=10^3$
$X_i$,$Y_i$は$i$番目の点$P_i$の座標。$0\le X_i,Y_i \le 1000000000=10^9$
$i \neq j $であれば$(X_i,Y_i) \neq (X_j,Y_j)$
座標の1単位の長さは$1cm$である。

出力

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

サンプル

サンプル1
入力
3
0 0
10 10
15 14
出力
20

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

サンプル2
入力
3
0 0
10 10
5 5
出力
10

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

サンプル3
入力
2
0 0
1000000000 1
出力
1000000010

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

サンプル4
入力
10
22332 32623
1203 95262
31305 81403
22442 55471
89784 78507
63397 32214
67779 12590
991 97116
79915 80450
6595 94117
出力
27790

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。