No.168 ものさし
タグ : / 解いたユーザー数 193
作問者 :
nmnmnmnmnmnmnm
/ テスター :
kroton
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。