Problem G
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.)
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.
Input
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$.
Output
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 |
