Laser Cutter

Time Limit : 5 sec, Memory Limit : 262144 KB

Problem H: Laser Cutter

Ciel is going to do woodworking. Ciel wants to make a cut in a wooden board using a laser cutter.

To make it simple, we assume that the board is a two-dimensional plane. There are several segments on the board along which Ciel wants to cut the board. Each segment has a direction and Ciel must cut those segments along their directions. Those segments are connected when you ignore the directions, that is, any two points on the segments are directly or indirectly connected by the segments.

While the laser cutter is powered on, it emits a laser which hits the board at a point and cuts the board along its trace. The laser initially points to $(x, y)$. Ciel can conduct the following two operations:

  • Move the laser cutter with its power on and cut (a part of) a segment along its direction, or
  • Move the laser cutter to any position with its power off. Ciel should not necessarily cut the whole segment at a time; she can start or stop cutting a segment at any point on the segments.

Ciel likes to be efficient, so she wants to know the shortest route such that the laser cutter cuts the whole parts of all the segments and then move back to the initial point. Your task is to write a program that calculates the minimum total moving distance of the laser cutter.


The first line of the input contains an integer $n$ ($1 \leq n \leq 300$), the number of segments. The next line contains two integers $x$ and $y$ ($-1,000 \leq x, y \leq 1,000$), which is the initial position $(x, y)$ of the laser. The $i$-th of the following $n$ lines contains four integers $sx_i$, $sy_i$, $tx_i$ and $ty_i$ ($-1,000 \leq sx_i, sy_i, tx_i, ty_i \leq 1,000$), which indicate that they are the end points of the $i$-th segment, and that the laser cutter can cut the board in the direction from $(sx_i, sy_i)$ to $(tx_i, ty_i)$. The input satisfies the following conditions: For all $i$ ($1 \leq i \leq n$), $(sx_i, sy_i) \ne (tx_i, ty_i)$. The initial point $(x, y)$ lies on at least one of the given segments. For all distinct $i, j$ ($1 \leq i, j \leq n$), the $i$-th segment and the $j$-th segment share at most one point.


Output a line containing the minimum total moving distance the laser cutter needs to travel to cut all the segments and move back to the initial point. The absolute error or the relative error should be less than $10^{-6}$.

Sample Input

0 1
0 0 0 1
0 1 0 2
0 2 0 3

Output for the Sample Input


Sample Input

0 1
0 0 0 2
-1 1 1 1

Output for the Sample Input


Sample Input

0 0
0 0 1 0
1 1 -1 1
-1 1 -1 -1
-1 -1 1 -1
1 -1 1 1

Output for the Sample Input


Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 4, Tokyo, Japan, 2015-09-14