Under construction

Still being built. Things may change

Leaps Tall Buildings (in a Single Bound)

Time limit1sMemory limit128 MB

Summary
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 aa and an initial vertical velocity vv, his height after tt seconds is d(t)=v t+12 a t2d(t) = v\,t + \tfrac{1}{2}\,a\,t^2. 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 d1+d2+⋯+dnd_1 + d_2 + \cdots + d_n metres. Segment ii has width did_i; the first and last segments are open ground (height 00), and each interior segment ii is a building of height hih_i that Superman must clear over its entire width. Heights and widths may be non-integers. nn is at most 100100. 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

Examples2

  1. Example 1

    Input
    3
    0 5
    10 5
    0 5
    5
    0 10.5
    20 11.5
    25 10
    10 15
    0 7
    
    Expected output
    11.25
    31.92
    
  2. Example 2

    Input
    3
    0 10
    6 10
    0 10
    
    Expected output
    6.75