Minimum Time Through Road Segments

Xiao Ming rides his bicycle every morning to class. His route consists of \( n \) road segments. In the \( i\)-th segment, the length is \( w_i \) (in meters), the speed limit is \( s_i \) (in m/s), and the absolute value of the acceleration is bounded by \( a_i \) (in m/s²). At any time on a segment, his speed cannot exceed the speed limit, and he can accelerate or decelerate with an acceleration whose absolute value does not exceed \( a_i \). He starts from rest (i.e. initial speed is \(0\) m/s). Your task is to compute the minimum time required for Xiao Ming to travel through all the segments.

The optimal strategy in a segment is to use maximum acceleration until reaching a peak speed (which is limited by both the speed limit \( s_i \) and the need to decelerate if the next segment requires a lower starting speed), then (if necessary) cruise at the maximum speed, and finally decelerate if the next segment imposes a lower speed constraint. In particular, if a segment is traversed with constant acceleration \( a \) (whether accelerating or decelerating) from an initial speed \( u \) to a final speed \( v \), the distance covered is:

[ d = \frac{|v^2 - u^2|}{2a}. ]

If the distance \( w \) is larger than \( d \), then the extra distance is covered at constant speed \( \max(u,v) \). Consequently, the time spent on the segment is computed as:

• If \( v \ge u \): \[ T = \frac{v - u}{a} + \frac{w - \frac{v^2 - u^2}{2a}}{v}. \]
• If \( u > v \): \[ T = \frac{u - v}{a} + \frac{w - \frac{u^2 - v^2}{2a}}{v}. \]

The overall strategy is to plan the speeds on each segment by a forward pass (computing the maximum possible speed achievable under acceleration and the segment limit) and a backward pass (adjusting speeds to permit necessary deceleration for upcoming segments). Finally, sum up the time for each segment. It is guaranteed that the answer computed using an optimal strategy will pass all test cases.

inputFormat

The first line contains an integer \( n \) (the number of road segments). Each of the following \( n \) lines contains three real numbers \( w_i \), \( s_i \), and \( a_i \), representing the length (in meters), the speed limit (in m/s), and the maximum acceleration (in m/s²) for the \( i\)-th segment.

outputFormat

Output a single real number: the minimum time (in seconds) required for Xiao Ming to traverse all segments. The answer must be accurate to at least 6 decimal places.

sample

1
100 10 10

10.500000