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 MSDOS
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
AIcontrolled gorilla! (Or a humancontrolled gorilla, for that
matter.)
Trajectory of first sample input
We all learned that a projectile such as an explosive
banana travelling under the influence of gravity, neglecting
and external influences like wind or air resistance (which
we’ll ignore), will follow a perfectly parabolic path. Thus, if
$x$ is the horizontal
direction and
$y$ the
vertical direction,
$(x,
y)$ positions on the projectile’s path can be described
by an equation
$y = Ax^2 + Bx +
C$, where
$A$,
$B$, and
$C$ are real numbers. Atrebla is on
the left, which means the path must start at the left gorilla’s
position, end at the right gorilla’s position, and necessarily
avoid all obstacles (buildings) by flying over them.
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
