C - THE☆たこ焼き祭り2012 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

たこ焼き屋の開店にあたって、たこ焼きの味を皆に分かってもらうために試食イベントを行うことにしました。
しかし、高橋社長はたこ焼きをより多くの人に食べてもらいたいので、試食イベントを兼ねたお祭り『THE☆たこ焼き祭り2012』をすることを提案してきました。高橋社長が提案してきた『THE☆たこ焼き祭り2012』の試食イベント内容は以下のようになっています。

会場にはあなたと参加者を足して N 人の人がいます。あなたはたこ焼きを N 個持っており、それを全員に 1 人 1 個ずつ行き渡るようにします。
会場は広いのであなたはたこ焼きを投げて配らないといけません。 あなただけで全員に配ることは大変なので、参加者にも協力してもらうことにし、参加者は受け取ったたこ焼きを別の参加者へと投げることもできます。
あなたと参加者はつまようじを1 人につき 1 本しか持っていないので同じタイミングで複数のたこ焼きを投げることはできず、たこ焼きを投げてから 1 秒間は次のたこ焼きを投げることができません。受け取る側はいつでも何個でも受け取ることができます。
さらに、あなたと参加者は立っている位置から動いてはいけません。
参加者は大人から子供までいるのでそれぞれにはたこ焼きをキャッチできる速度の上限があり、たこ焼きを投げる側にも投げられる速度の上限があります。投げられたたこ焼きの速度は減衰することなく受け取り手に届きます。

たこ焼きはなるべく出来立てを食べて欲しいので、たこ焼きを全員に配り切るために必要な時間の最小値を答えなさい。

入力

入力は以下の形式で標準入力から与えられる。 
N
x_{0} y_{0} t_{0} r_{0}
x_{1} y_{1} t_{1} r_{1}
:
:
x_{N-1} y_{N-1} t_{N-1} r_{N-1}
  • 入力は N+1 行ある。
  • 1 行目には、たこ焼き祭りの参加者数とあなたを足した数を表す整数 N\ (1≦N≦1,000) が与えられる。
  • 2 行目には、あなたが立っている位置の x 座標を表す整数 x_0\ (-10,000≦x_0≦10,000)、y 座標を表す整数 y_0\ (-10,000≦y_0≦10,000)、たこ焼きを投げる速度の上限を表す整数 t_0\ (3≦t_0≦340) とたこ焼きを受け取る速度の上限を表す整数 r_0\ (3≦r_0≦340) が空白で区切られて与えられる。
  • 3 行目から N-1 行のうち i+2\ (1≦i≦N-1) 行目には i 番目の参加者が立っている位置の x 座標を表す整数 x_i\ (-10,000≦x_i≦10,000)、y 座標を表す整数 y_i\ (-10,000≦y_i≦10,000)、たこ焼きを投げる速度の上限を表す整数 t_i\ (3≦t_i≦340) とたこ焼きを受け取る速度の上限を表す整数 r_i\ (3≦r_i≦340) が空白で区切られて与えられる。
  • 与えられる速度は 1 秒辺りの速度である。
  • 複数の人が同じ位置に立つことはない。

出力

たこ焼きを全ての参加者が 1 つずつ受け取るためまでに必要な秒数の最小値を 1 行で出力せよ。
出力は整数および小数のみとし、誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容する。
なお、最後には改行を出力せよ。

入力例 1

4
0 0 300 10
0 100 10 100
0 200 10 200
0 300 10 300

出力例 1

3
  • 0 秒目 :
    • あなた : 1 番目の参加者に速度 100 でたこ焼きを投げる。
  • 1 秒目 :
    • あなた : 2 番目の参加者に速度 200 でたこ焼きを投げる。
    • 1 番目の参加者 : あなたが 0 秒目に投げたたこ焼きをキャッチする。
  • 2 秒目 :
    • あなた : 3 番目の参加者に速度 300 でたこ焼きを投げる。
    • 2 番目の参加者 : あなたが 1 秒目に投げたたこ焼きをキャッチする。
  • 3 秒目 :
    • 3 番目の参加者 : あなたが 2 秒目に投げたたこ焼きをキャッチする。

入力例 2

4
0 0 100 10
0 90 10 10
0 100 30 100
-20 100 10 10

出力例 2

3
  • 0 秒目 :
    • あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
  • 1 秒目 :
    • あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
    • 2 番目の参加者 : あなたが 0 秒目に投げたたこ焼きをキャッチし、3 番目の参加者に速度 10 で投げる。
  • 2 秒目 :
    • あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
    • 2 番目の参加者 : あなたが 1 秒目に投げたたこ焼きをキャッチし、2 番目の参加者に速度 10 で投げる。
  • 3 秒目 :
    • 1 番目の参加者 : 2 番目の参加者が 2 秒目に投げたたこ焼きをキャッチする。
    • 2 番目の参加者 : あなたが 2 秒目に投げたたこ焼きをキャッチする。
    • 3 番目の参加者 : 2 番目の参加者が 1 秒目に投げたたこ焼きをキャッチする。

入力例 3

1
0 0 3 3

出力例 3

0
  • 参加者があなただけなので配る必要がありません。

入力例 4

4
58 -49 38 109
45 -29 200 56
-32 123 103 98
49 -234 289 43

出力例 4

4.874179

入力例 5

8
100 100 30 50
100 50 93 123
100 0 89 111
50 100 13 18
50 0 155 86
0 100 30 58
0 50 58 49
0 0 98 153

出力例 5

7.666667

出典

ARC 008