Problem H
Helpful Rotations

Relatively close to Mars, there is a small group of space habitats shaped as discs. To make movement between them easy, they are all perfectly aligned in the Z coordinate. But while movement is usually easy, there are cases when it’s not:

“Hey Sophia, this situation reminds me of that story you told about your father” Galatea said. “Oh, the one where he had issues getting back to our castle? Well.. sure, it was a kind of ship, and had steering problems too. I don’t care about how many ways we can get to a space habitat with a repair station though” Sophia replied. Galatea had tried to fix their steering engines, but quickly figured that they needed to get to a proper repair station.

Sophia’s spaceship is an older model, with some rather weird quirks. For one, the ship must either have its nose or tail faced directly at the habitat’s centre to dock. It also has engines on its nose; so while they can’t steer in any direction right now, they can accelerate and decelerate at $a$ clicks per second.

“I guess we can jump from habitat to habitat by just waiting, right? The habitats rotate with a fixed speed; at some point we’ll point towards some other habitat’s centre.” she explained. “That’ll probably take ages though, and you forget the abandoned habitats: They decided to stop their rotation for safety reasons, right?” Sophia muttered. “I’m not so sure…I do recall some habitats spinning really fast, so it may be faster than waiting for the repair bots.” Galatea argued. “I highly doubt that, but we’ll see. Computer, find the fastest path to a space habitat with a repair station.”

Figure 1: Visualisation of Sample Input 1, and the fastest path to the repair station habitat.

Input

The first line consists of $2$ integers followed by $2$ real numbers: $H$, $H_{start}$, $\theta _{start}$ and $a$. $H$ is the number of space habitats, $H_{start}$ is the habitat Galatea and Sophia are at, and $\theta _{start}$ is their current angle in radians. The max acceleration of their spaceship is $a$ clicks per second.

Then follows $H$ lines, one representing each habitat. Each line consists of $4$ real numbers $x_ i$, $y_ i$, $r_ i$ and $\omega _ i$, along with a single character $R_ i$. The real numbers represent a circle with centre at $(x_ i, y_ i)$ and a radius of $r_ i$ clicks, spinning at $\omega _ i$ radians per second. $R_ i = \texttt{t}$ if there is a repair station at the habitat, f otherwise.

Output

Print out the time it takes to get from their current location to a space habitat with a proper repair station. Your answer must have an absolute or relative error of at most $10^{-6}$.

If their ship is unable to reach a space habitat with a proper repair station, print out request repair bot assistance instead.

Limits and Additional Notes

• $0 \leq H_{start} < H \leq 175$

• $0 \leq \theta _{start} < 2\pi $

• $1.0 \leq a \leq 11.2$

• $0 \leq x_ i, y_ i < 10\, 000$, $1.0 \leq r_ i \leq 100.0$

• For all $i \neq j$, $r_ i + r_ j + 1 \leq \sqrt{|x_ i-x_ j|^2+|y_ i-y_ j|^2}$

• $-4\pi \leq \omega _ i \leq 4\pi $

• $R_ i \in \{ \texttt{t}, \texttt{f}\} $

• All real numbers in the input have at most $4$ digits after the decimal point.

• Sophia’s spaceship is small enough to be considered a point.

• A valid travel path from one space habitat $i$ to $j$ must not intersect with or touch any other habitat.

• Both the docking and undocking procedure is instantaneous. When docking, the spaceship must have zero velocity, and when undocking, the velocity caused by the habitat’s rotation is cancelled.

• Floating point inaccuracies for nonzero numbers will not result in wildly different results. More precisely: a relative change in the real number inputs of at most $10^{-8}$ will result in an absolute or relative change in the accepted answer by at most $10^{-6}$.

6 0 0.78 9.87
0.0 0.0 8.0 -1.3 f
60.0 3.0 14.0 0.3 f
25.0 30.0 20.0 0.0 f
8.0 75.0 7.0 0.2 f
17.0 58.0 7.0 5.0 f
55.0 70.0 10.0 1.0 t

17.62702752357573

4 3 1.0 4.0
0.0 20.0 20.0 1.2345 t
50.0 0.0 30.0 0.0 f
80.0 40.0 5.0 2.1 f
100.0 20.0 20.0 -3.1 f

12.968636660192796