Problem J
Careful Ascent

That went well! As police sirens rang out around the palace, Mal Reynolds had already reached his lifting device outside of the city.

No spaceship can escape Planet Zarzos without permission from the High Priest. However, Mal’s spaceship, Firefly, is in geostationary orbit well above the controlled zone and his small lifting device can avoid being recognised as an intruder if its vertical velocity is exactly $1$ km/min.

There are still two problems. First, Mal will not be able to control the vehicle from his space suit, so he must set up the autopilot while on the ground. The vertical velocity must be exactly $1$ km/min and the horizontal velocity must be set in such a way that Mal will hit the Firefly on the resulting trajectory. Second, the energy shields of the planet disturb the autopilot: They will decrease or increase the horizontal velocity by a given factor. The original horizontal velocity is restored as soon as there is no interference. For this problem we consider Firefly to be a single point – the shape shown in Figure 1 is merely for decorative purposes.

\includegraphics[width=0.6\textwidth ]{sample1.pdf}
Figure 1: Illustration of Sample Input 1.

Luckily, Mal recorded the positions of the shields and their influence on the autopilot during his descent. What he needs now is a program telling him the right horizontal velocity setting.


The input consists of:

  • one line with two integers $x$, $y$ ($-10^7 \le x \le 10^7$, $|x| \le y \le 10^8$ and $1 \le y$), Firefly’s coordinates relatively to Mal’s current position (in kilometres).

  • one line with an integer $n$ ($0 \le n\le 100$), the number of shields.

  • $n$ lines describing the $n$ shields, the $i$th line containing three numbers:

    • an integer $l_ i$ ($0 \le l_ i < y$), the lower boundary of shield $i$ (in kilometres).

    • an integer $u_ i$ ($l_ i < u_ i \le y$), the upper boundary of shield $i$ (in kilometres).

    • a real value $f_ i$ ($0.1 \le f_ i \le 10.0$), the factor with which the horizontal velocity is multiplied during the traversal of shield $i$.

    It is guaranteed that shield ranges do not intersect, i.e., for every pair of shields $i \ne j$ either $u_ i\le l_ j$ or $u_ j\le l_ i$ must hold.

    All real numbers will have at most $10$ digits after the decimal point.


Output the horizontal velocity in km/min which Mal must choose in order to reach Firefly. The output must be accurate to an absolute or relative error of at most $10^{-6}$.

Sample Input 1 Sample Output 1
100 140
40 90 0.2000000000
Sample Input 2 Sample Output 2
100 100
0 20 2.0000000000
50 100 0.1000000000
20 50 0.2000000000

Please log in to submit a solution to this problem

Log in