問題一覧 > 通常問題

No.1413 Dynamic Sushi

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 37
作問者 : evima / テスター : 37zigen iaNTU
お気に入りにしたユーザー ProblemId : 5888 / 自分の提出
問題文最終更新日: 2021-03-05 09:33:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
1時間コンテスト02 (順位表) の他の問題:

Problem Statement

The Japanese restaurant "Dynamic Sushi" is a huge establishment equipped with many conveyor belts. In what follows, we regard the inside of the restaurant as a coordinate plane.
Currently, $N$ plates of sushi are circulating in the restaurant; we call them Sushi $1$, $\cdots$, Sushi $N$.
Sushi $i$ $(1 \leq i \leq N)$ is located at the coordinates $(X_i + R_i \cos((V_i t + A_i) \pi / 180), Y_i + R_i \sin((V_i t + A_i) \pi / 180))$ at time $t$ $(t \geq 0)$.
(Multiple sushi may be located at the same coordinates at the same time, but no collisions occur because the conveyor belts have different heights.)

Runrun has entered this restaurant and was led to the coordinates $(0, 0)$ at time $0$.
Runrun can move freely around the restaurant at a speed of at most $W$ per second, and when located at the same coordinates as a sushi, can eat that sushi in $0$ seconds.
Here, it is guaranteed that Runrun can move faster than the rotation speed of any sushi. That is, $|R_i V_i \pi / 180| < W$ for all $i$ $(1 \leq i \leq N)$.
Find the minimum time required for Runrun to eat all $N$ plates of sushi. The sushi may be eaten in any order.

Input

$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$
  • All values in the input are integers.

Output

Output the answer as a real number, followed by a newline.
Your answer is judged as correct if its absolute or relative error from the solution prepared by evima is at most $10^{-5}$.

Sample

Sample 1
Input
3 2
2 3 1 -45 0
2 -2 2 30 60
3 0 3 0 90
Output
2.70710678118655

An optimal way of moving is as follows.

  • From time $0$, for $1$ second, move in the positive $x$-axis direction at a speed of $2$ per second, and eat Sushi $2$ at the coordinates $(2, 0)$.
  • From time $1$, for $1$ second, move in the positive $y$-axis direction at a speed of $2$ per second, and eat Sushi $1$ at the coordinates $(2, 2)$.
  • From time $2$, for $\sqrt{2} / 2$ seconds, move in the direction of the vector $(1, 1)$ at a speed of $2$ per second, and eat Sushi $3$ at the coordinates $(3, 3)$.
Sample 2
Input
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
Output
0

Multiple sushi may circulate in exactly the same way.
Also, there may be a sushi at $(0, 0)$ at time $0$.

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