問題一覧 > 通常問題

No.168 ものさし

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 193
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : krotonkroton
4 ProblemId : 296 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:44

問題文

$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。