実行時間制限: 5.252 sec / メモリ制限: 246 MB
問題文
dwango社に新しいオフィスができました。今日は、そのオフィスで仕事が行われる最初の日です。
社員のニワンゴくんは朝オフィスに行こうとして、オフィスの最寄り駅に着いたところで大変なことに気付きました。なんと、オフィスの場所を知らなかったのです。
dwango社の新しいオフィスはある 1 本の道路上にあり、オフィスの最寄り駅は座標 0 にあります。 道路には交差点が N 個あり、ニワンゴくんはその N 個の交差点のうちのどれかにオフィスがあることを知っています。 負の座標にオフィスがあるかもしれません。 なお、駅のある座標 0 に交差点はないものとします。
仕方がないので、ニワンゴくんはこの道路上を歩き回ってオフィスを探すことにしました。 ニワンゴくんは交差点のある座標に着いたとき、またその時のみ、そこにオフィスがあるかどうかがわかります。
さて、ニワンゴくんの上司はニワンゴくんが駅に着いた時刻を知っています。 dwango社の社員はみな単位時間に単位距離進む速度で歩くので、駅からオフィスまでの距離を x として、ニワンゴくんが駅に着いた時刻を0とすると、 ニワンゴくんがオフィスに着くのが時刻 x よりあとになると、ニワンゴくんは怒られてしまいます。時刻 x より前になるぶんにはかまいません。
そこでニワンゴくんは、常に一定の速度で走って移動することで、オフィスがどの交差点にある場合でも、駅とオフィスの間の距離が x であるならば時刻 x までに オフィスに到着することを考えました。ニワンゴくんはなるべくゆっくり走りたいので、適切な移動経路を選んで、走る速度を最小にすることにしました。
ニワンゴくんの走る速度としてありうる最小の値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N x_1 . . . x_N
- 1 行目には、整数 N(1 ≦ N ≦ 1000) が与えられる。
- 続く N 行には、 i 番目の交差点の位置を表す整数 x_i(-10^9 ≦ x_i ≦ 10^9, x_i ≠ 0) が与えられる。任意の i(1 ≦ i ≦ N-1) に対し、 x_i < x_{i+1} を満たす。
部分点
この問題には部分点が設定されている。
- N ≦ 200 を満たすデータセットに正解した場合、部分点として 70 点が与えられる。
- すべてのデータセットに正解した場合、追加で 50 点が与えられ、合計で 120 点となる。
出力
ニワンゴくんの走る最小の速度を 1 行に出力せよ。小数点以下何桁まで出力してもかまわないが、真の値との絶対誤差あるいは相対誤差が 10^{-9} 以下のとき正答とみなされる。
出力の最後には改行を忘れないこと。
入力例1
4 -3 -1 1 2
出力例1
3.00000000000000
ニワンゴくんの動きの例として、以下のものが挙げられます。
- 速度 3で 2 番目の交差点に移動し、そこがオフィスかどうか判定する。
- オフィスでなければ、速度 3 で 3 番目の交差点に移動し、そこがオフィスかどうか判定する。
- オフィスでなければ、速度 3 で 4 番目の交差点に移動し、そこがオフィスかどうか判定する。
- オフィスでなければ、速度 3 で 1 番目の交差点に移動し、そこがオフィスかどうか判定する。
この行動をとった場合、 1,2,3,4 番目の交差点には順に 3,1/3,1,4/3 単位時間で移動することができるので、問題文の条件を満たします。
入力例2
5 -5 -2 2 4 7
出力例2
4.14285714285714
入力例3
9 -18 -13 -11 -6 -2 1 6 16 17
出力例3
4.37500000000000