Directed Segment Coverage

In this problem, you are given n directed line segments on an infinite 2D plane. Each segment is specified by two endpoints; the segment must be traversed completely in the given direction (from its first endpoint to its second) in order to "cover" it. You can traverse a segment in parts (i.e. leave it midway and later re-enter it) as long as the union of all traversals along that segment covers the entire segment in the prescribed direction. Note that if two segments share a common portion with the same direction, traversing that overlapping portion counts for both segments.

Your task is to determine the shortest closed path that covers all the n directed segments. The path is constructed by connecting the segments with free movement in the plane. More formally, you must choose a sequence (or permutation) of the segments and decide on points within each segment such that you travel along each segment (thus incurring a cost equal to its Euclidean length) and, between consecutive segments (and from the last back to the first), you travel along a connecting path in the plane. Since you are free to choose where to start and where to leave/enter a segment, the extra cost of moving between segments is the minimum distance between any point on one segment and any point on the next. The overall cost is thus the sum of the lengths of all segments plus the connecting distances. You are to output this minimum total distance. Formally, if the i^th segment (with endpoints \(A_i\) and \(B_i\)) has length \(L_i = |B_i - A_i|\) and if the minimum distance from segment \(i\) to segment \(j\) is defined as

\(d(i,j)=\min_{p \in \overline{A_iB_i},\; q \in \overline{A_jB_j}} \|p-q\|\),

then, if we select an ordering \(\pi\) (a cyclic permutation of \(\{1,2,\ldots,n\}\)) the total cost is

\(\sum_{i=1}^n L_{\pi(i)} + \sum_{i=1}^{n} d(\pi(i), \pi(i+1))\),

with \(\pi(n+1)=\pi(1)\). Output the minimum total cost. It is guaranteed that an optimal solution exists.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 15), the number of directed segments.

Then follow n lines, each containing four real numbers x1 y1 x2 y2 representing the starting point \((x1,y1)\) and the ending point \((x2,y2)\) of a directed segment. All numbers have at most 6 digits after the decimal point.

outputFormat

Output a single line with a real number representing the minimum total distance required to cover all directed segments in a closed tour. The answer is considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

1
0 0 1 0

1.000000