Gorillas

Do you remember playing the video game Gorillas? It was originally released in 1991 by IBM corporation as demonstration of what you can do with the QBasic programming language. The game caught like wildfire among programmers who owned an MS-DOS computer of those days, and as they say, the rest is history.

In the game, up to two players control gorillas who take turns throwing explosive bananas at each other above a city skyline. The players can adjust the angle and velocity of each throw, and the objective is to hit the other player’s gorilla with your banana.

Atrebla remembers this game well, and she still loves playing it. The only part she didn’t like was being beaten by the AI. And that’s why she’s now asking for your help to come up with an algorithm that will knock the socks off of any AI-controlled gorilla! (Or a human-controlled gorilla, for that matter.)

Trajectory of first sample input

There are still an infinite number of project paths that
satisfy this condition, so let’s add one more condition. One
problem with the original game was that if somebody launched a
banana high up into the air, the players had to wait
*forever* for it to come back down before they could
continue playing. Nobody wants that! Thus, given the positions
of the two gorillas, and the obstacles in between, your job is
to find the parabolic projectile path that reaches the
*lowest* maximum height, yet successfully clears all
obstacles to hit the target gorilla on the right.

The input begins with an integer $1 \leq T \leq 20$, the number of test cases.

Each test case begins with four integers, $x_ s \; y_ s \; x_ t \; y_ t$, which indicate the positions of Atrebla’s gorilla and the target gorilla, respectively. The next line contains an integer $N$, indicating the number of obstacles that exist between the gorillas ($0 \le N \le 1000$). Finally, $N$ lines of text follow, each containing two integers, $x_ i \; y_ i$, describing the position and height of each obstacle between the gorillas ($x_ s < x_ i < x_ t$). Horizontal distance is measured along the $x$-axis, and height is measured on the $y$-axis, with gravity acting in the $-y$ direction. All coordinates lie in the ranges $0 \le x \le 10\, 000$ and $0 \le y \le 10\, 000$.

The output consists of a single real number for each test case: the highest altitude ($y$-coordinate) that your explosive banana, which originates from the left gorilla and hits the target gorilla, will reach if it follows the parabolic projectile path with lowest maximum height. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-5}$.

Sample Input 1 | Sample Output 1 |
---|---|

3 0 0 16 0 1 8 8 0 10 72 1 4 24 25 11 19 59 14 42 10 10 100 1000 100 0 |
8.00000 26.0000 100.000 |