Fencing the Ravines

You have discovered an endless field in which you’ve forgotten your fragmented, painful past. Like a child, you run in the open fields of God’s grace, reminiscent of the lyrics of Open Fields of Grace by Jackie Evancho (music by Lisa Venkatrathnam and Paul Sumares).

However, danger lurks in the form of several ravines cutting through the field. Each ravine is represented as a line segment (their widths are negligible and they may intersect each other) and you risk falling into any one of them at any moment.

To run freely, you plan to install fences. A fence is defined to be a closed, simple (non self-intersecting) curve. You are allowed to build one or more fences, but they must be pairwise disjoint (i.e. no two fences cross each other). The requirement is that every ravine must lie completely inside the region enclosed by some fence.

Installing a fence uses resources proportional to its length. In order to minimize the resource consumption, you want to determine the infimum of the total fence length required. In other words, find the largest real number \(x\) such that no valid fencing scheme has total length less than \(x\).

Mathematical Note: For any closed curve \(C\) enclosing a set \(S\subset \mathbb{R}^2\), the minimum achievable length is given by the perimeter of the convex hull \(\mathrm{conv}(S)\) if \(S\) is non-collinear. For collinear points (or a degenerate convex hull), the infimum is \(2L\), where \(L\) is the maximum distance between any two points. When building fences for a subset of ravines, you are free to group them arbitrarily. The cost of a fence for a group is defined as:

• If all endpoints of the ravines in the group are collinear, the cost is \(2\times d\), where \(d\) is the distance between the two farthest points.
• Otherwise, the cost is the perimeter of the convex hull of all endpoints in the group (which can be expressed in LaTeX as \(P = \sum_{i=1}^{k} \|p_i-p_{i+1}\|\)).

Your task is to choose a partition of the given ravines (each ravine must belong to exactly one group) and then, for each group, build a fence with the aforementioned cost. The goal is to minimize the sum of costs over all groups. Output this infimum value with a precision of 6 decimal places.

inputFormat

The first line contains a positive integer \(n\) (\(1 \le n \le 15\)), the number of ravines.

Then follow \(n\) lines. Each of these lines contains four integers \(x_1\ y_1\ x_2\ y_2\) specifying the coordinates of the endpoints of a ravine. Coordinates are given as integers and their absolute values do not exceed \(10^4\).

outputFormat

Output a single line with a real number: the infimum of the total fence length required. The answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

1
0 0 1 0

2.000000