[ARC008C] THE☆たこ焼き祭り2012

在章鱼烧店开店之际，为了让大家了解章鱼烧的味道，决定举行试吃活动。 但是，高桥社长为了让更多的人吃到章鱼小丸子，提议举行试吃活动兼庆典“THE☆章鱼小丸子庆典2012”。高桥社长提议的“THE☆章鱼烧祭2012”的试吃活动内容如下。 会场上加上你和参加者共有N N人。你有N N个章鱼小丸子，每个人1人一个一个地把它普及。 因为会场很大，所以你必须把章鱼小丸子扔出去分发。因为只靠你分发给全员是很困难的，所以也请参加者协助，参加者也可以把收到的章鱼烧扔给别的参加者。 因为你和参加者1人1个牙签只有1个1个，所以不能在同一时刻投出多个章鱼小丸子，投出章鱼小丸子后的1秒内不能投下一个章鱼小丸子。接收方随时都可以接收几个。 而且，你和参加者不能从站立的位置开始移动。 因为参加者从大人到小孩都有，所以每个人都有能抓住章鱼烧的速度上限，投章鱼烧的一方也有能投的速度上限。被扔了的章鱼小丸子的速度不会衰减到收信人手中。 因为想让章鱼小丸子尽量吃刚做好的，所以请回答把章鱼小丸子分发给所有人所需时间的最小值。

[problemUrl]: https://atcoder.jp/contests/arc008/tasks/arc008_3 たこ焼き屋の開店にあたって、たこ焼きの味を皆に分かってもらうために試食イベントを行うことにしました。 しかし、高橋社長はたこ焼きをより多くの人に食べてもらいたいので、試食イベントを兼ねたお祭り『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} $ 以下であれば許容する。 なお、最後には改行を出力せよ。 ``` 4 0 0 300 10 0 100 10 100 0 200 10 200 0 300 10 300 ``` ``` 3 ``` - $ 0 $ 秒目 : - あなた : $ 1 $ 番目の参加者に速度 $ 100 $ でたこ焼きを投げる。 - $ 1 $ 秒目 : - あなた : $ 2 $ 番目の参加者に速度 $ 200 $ でたこ焼きを投げる。 - $ 1 $ 番目の参加者 : あなたが $ 0 $ 秒目に投げたたこ焼きをキャッチする。 - $ 2 $ 秒目 : - あなた : $ 3 $ 番目の参加者に速度 $ 300 $ でたこ焼きを投げる。 - $ 2 $ 番目の参加者 : あなたが $ 1 $ 秒目に投げたたこ焼きをキャッチする。 - $ 3 $ 秒目 : - $ 3 $ 番目の参加者 : あなたが $ 2 $ 秒目に投げたたこ焼きをキャッチする。 ``` 4 0 0 100 10 0 90 10 10 0 100 30 100 -20 100 10 10 ``` ``` 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 $ 秒目に投げたたこ焼きをキャッチする。 ``` 1 0 0 3 3 ``` ``` 0 ``` - 参加者があなただけなので配る必要がありません。 ``` 4 58 -49 38 109 45 -29 200 56 -32 123 103 98 49 -234 289 43 ``` ``` 4.874179 ``` ``` 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 ``` ``` 7.666667 ```