No.1413 Dynamic Sushi
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
evima
37zigen