Problem C
Checkpoint Champion

Chester is the best orienteerer at IDI, being the undefeated champion for what seems like an eternity. His navigation skills mean he is able to find the control points almost immediately, and usually finds the optimal path to the next control point.

This is a problem, as many people feel disheartened whenever they first join the orienteering club at IDI. “There’s no way I can get to that level,” they think, and usually stop participating in competitions after a month or two.

The orienteering committee has therefore started to make a new type of sport which focuses more on speed and less on navigational skills: Line segment orienteering. By replacing the control points with line segments, they think they can increase the number of participants significantly. And they have decided to utilize GPS for what it’s worth: Instead of using an e-card they “punch” at the station, their location will automatically check them in. This means the participant won’t have to look hard after a control point, and they don’t have to stop to punch their card either.

Of course, this changes the rules of orienteering somewhat: In line segment orienteering, every participant starts at the point $S = (s_ x, s_ y)$. They then have to touch the line segments $\overline{L_{i}R_{i}}$ for $i = 1, 2 \ldots N$ in order, and the fastest person to reach the last line segment wins. You are allowed to touch a line segment $i$ before and after you have touched segment $i-1$, but you still have to touch it again after you touch line segment $i-1$.

Figure 1: Solutions for sample inputs 1 and 2, respectively.

However, certain test runs reveal that the GPS is not as accurate as they want it to be: If a participant doesn’t cross the line segment, the system doesn’t always detect that the participant touches the segment. As the competitors are very competitive, this could be disastrous. To safeguard against this situation, they decide to ensure that the shortest path to the next line segment is always in front of the current line segment.

But now they have another problem: They don’t know how to compute the course’s length! Previously they used the straight line segments between the control points as a lower bound, but with these line segments, they would have to redo their computations. Can you help them?

Input

The first line contains three integers $N$, $s_ x$ and $s_ y$, denoting the number of line segment checkpoints and the initial starting location $S = (s_ x, s_ y)$. Then follows $N$ lines, each with 4 integers $l_{i,x}$, $l_{i,y}$, $r_{i,x}$, $r_{i,y}$, denoting the location of the $i$th checkpoint. The left point on the line segment is $L_ i = (l_{i,x}, l_{i,y})$ and the right point on the line segment is $R_ i = (r_{i,x}, r_{i,y})$.

Output

Output the distance of the shortest path from the starting location to the last line segment checkpoint, which passes through all the intermediate segments in order. Your answer must have an absolute or relative error of at most $10^{-6}$.

Limits

• $0 < N \leq 5000$

• $-10\, 000 < l_{i,x}, l_{i,y}, r_{i,x}, r_{i,y} < 10\, 000$

• $R_0$ is right of $\overrightarrow {SL_0}$

• For all $1 < i \leq N$, let $A = L_{i-1}$, $B = R_{i-1}$, $C = R_{i}$ and $D = L_{i}$, be the vertices of the quadrilateral $\square ABCD$. Then, all the interior angles $0^{\circ } < \theta _0, \theta _1, \theta _2, \theta _3 < 180^{\circ }$:

  

4 -3 -1
0 0 0 -2
3 1 4 -3
7 0 7 -2
9 3 9 1

12.2859435986206797

3 0 0
4 3 6 0
4 5 5 7
-1 4 -1 6

12