ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Victim of Advertising

Time limit: 0.5 second
Memory limit: 64 MB
Figure-skater Lev is preparing for his fifth Olympic Games. Together with his coach he is inventing a new free skating program, which will win the judges' hearts and guarantee Lev a gold medal if he performs it without mistakes.
Lev practices twice a day, in the morning and in the evening. His wife is a well-known producer, and she wants to convert the time spent by her husband for practicing into money. She has signed a contract with the advertising agency “You See—You Buy,” which will shoot her husband at his training and make a cosmetics commercial with the use of this material.
So, n cameramen have come to Lev's training. They plan to shoot Lev performing his free skating program: the first cameraman will start the shooting, the second will continue, and so on. Each of the cameramen wants Lev to skate along a segment of a straight line from some point to another (and each has specified his own pair of points). Lev has decided to skate along all the specified segments passing from a segment to a segment along a circular arc so that his trajectory has the shape of a smooth curve. If there is no arc connecting two consecutive directed segments without breaks, Lev can extend one of the segments so as to connect them by an arc.
Lev has plotted a smooth curve passing through all the segments in the specified order, and now he is interested in finding the minimum time needed for skating along this curve. He knows that he cannot skate at a speed greater than 10 m/s or with a tangential acceleration greater than 1 m/s2 in magnitude (a tangential acceleration is the acceleration directed along the trajectory). Moreover, Lev cannot skate along circular arcs with a centripetal acceleration greater than 1 m/s2. Recall that a centripetal acceleration is calculated as v2/R, where v is the speed and R is the radius of the arc.

Input

The first line contains the integer n (1 ≤ n ≤ 1000). In the i-th of the following n lines you are given the coordinates of the beginning and of the end of the directed segment of a straight line specified by the i-th operator. The coordinates are integers and do not exceed 1000 in absolute value. No two consecutive segments are parallel and co-oriented. It is guaranteed that Lev can plot a smooth curve passing through all the segments.

Output

Output the minimum time (in seconds) Lev needs to skate along the smooth curve passing through the segments specified by the cameramen. Lev must start moving at the beginning of the first segment and finish at the end of the n-th segment. Lev's speed at the starting and finishing moments is zero. You must output the time with an absolute or relative error of at most 10−6.

Samples

inputoutput
1
0 0 4 0
4.0000000000
2
-2 4 0 4
4 0 4 -2
7.1415926536
Problem Author: Pavel Egorov
Problem Source: Ural Championship 2011
To submit the solution for this problem go to the Problem set: 1840. Victim of Advertising