問題一覧 > 通常問題

No.1413 Dynamic Sushi

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 31
作問者 : evimaevima / テスター : 37zigen37zigen iaNTUiaNTU
2 ProblemId : 5888 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-05 09:33:08

問題文

日本料理店「動的寿司」は多数のベルトコンベアが設置された巨大な店舗です。以下、店内を座標平面とみなします。
いま、店内では $N$ 皿の寿司が回っており、これらを寿司 $1$、$\cdots$、寿司 $N$ と呼びます。
寿司 $i$ $(1 \leq i \leq N)$ は、時刻 $t$ $(t \geq 0)$ に座標 $(X_i + R_i \cos((V_i t + A_i) \pi / 180), Y_i + R_i \sin((V_i t + A_i) \pi / 180))$ に位置します。
(複数の寿司が同じ時刻に同じ座標に位置することがありますが、ベルトコンベアの高さが違うため衝突は起こりません。)

ルンルンがこの店に入り、時刻 $0$ に座標 $(0, 0)$ に案内されました。
ルンルンは、店内を秒速 $W$ 以下で自由に動き回ることができ、寿司と同じ座標に位置するとその寿司を $0$ 秒で食べることができます。
ここで、ルンルンがどの寿司の回転速度よりも速く動けることが保証されます。すなわち、全ての $i$ $(1 \leq i \leq N)$ に対して $|R_i V_i \pi / 180| < W$ です。
ルンルンが $N$ 皿全ての寿司を食べるのに必要な最短の時間を求めてください。寿司を食べる順番は問いません。

入力

$N\ W$
$X_1\ Y_1\ R_1\ V_1\ A_1$
$:$
$X_N\ Y_N\ R_N\ V_N\ A_N$

  • $1 \leq N \leq 12$
  • $1 \leq W \leq 1000$
  • $-100 \leq X_i, Y_i \leq 100$
  • $1 \leq R_i \leq 100$
  • $-360 \leq V_i \leq 360$
  • $0 \leq A_i \leq 359$
  • $|R_i V_i \pi / 180| < W$
  • 入力中の全ての値は整数

出力

答えを実数として出力し、末尾で改行してください。
evima が用意した解答からの絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解と判定します。

サンプル

サンプル1
入力
3 2
2 3 1 -45 0
2 -2 2 30 60
3 0 3 0 90
出力
2.70710678118655

最適な移動方法は以下の通りです。

  • 時刻 $0$ から $1$ 秒間、$x$ 軸正方向に秒速 $2$ で進み、座標 $(2, 0)$ で寿司 $2$ を食べる。
  • 時刻 $1$ から $1$ 秒間、$y$ 軸正方向に秒速 $2$ で進み、座標 $(2, 2)$ で寿司 $1$ を食べる。
  • 時刻 $2$ から $\sqrt{2} / 2$ 秒間、ベクトル $(1, 1)$ の方向に秒速 $2$ で進み、座標 $(3, 3)$ で寿司 $3$ を食べる。
サンプル2
入力
12 1000
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
0 -100 100 360 90
出力
0

複数の寿司が全く同じ回り方をしているかもしれません。
また、時刻 $0$ に $(0, 0)$ に寿司があるかもしれません。

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