Leaps Tall Buildings (in a Single Bound)
Time limit1sMemory limit128 MB
Given a city skyline of buildings with widths and heights, find the lowest parabolic leap from ground to ground that clears every building, and print its peak altitude rounded to two decimals.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Math, Implementation
- Solved
- No attempts yet
Problem
It's a bird! It's a plane! It's coming right at us!
Although it sometimes seems otherwise, Superman cannot fly (without a plane). Instead he makes super-human leaps, especially over tall buildings. Since he never knows when he will have to catch a criminal, he cannot register flight paths; and to avoid colliding with planes he keeps every jump as low to the ground as he can.
A leap begins and ends at ground level, so Superman's trajectory is a parabola that is symmetric about the midpoint of the leap: under a downward gravitational acceleration and an initial vertical velocity , his height after seconds is . Given a city-scape, determine the smallest possible peak altitude (the maximum height Superman reaches during the leap) for which he still clears every building.
Input
The input consists of one or more city-scapes, each given as
n
0 d1
h2 d2
...
h(n-1) d(n-1)
0 dn
The leap starts and ends at ground level and covers a total horizontal distance of metres. Segment has width ; the first and last segments are open ground (height ), and each interior segment is a building of height that Superman must clear over its entire width. Heights and widths may be non-integers. is at most . Process city-scapes until the end of input.
Output
For each city-scape, print on its own line the minimum possible peak altitude - the smallest maximum height Superman can reach while still clearing every building - rounded to exactly two decimal places.
Hint
