Problem Description

Last night I saw you running
In the open fields of grace
No longer were you broken or in pain

The lyrics in the problem statement are from "Open Fields of Grace" by Jackie Evancho, composed by Lisa Venkatrathnam and Paul Sumares.

You have found an expansive field, and in this field, you have forgotten your broken and painful past. You run like a child in the grace of God.

However, you encounter a problem: there are several canyons in this field. You are at risk of falling into these canyons at any moment. To continue running freely, you decide to enclose these canyons with fences.

We can ignore the width of the canyons and consider each one as a line segment. These segments can intersect, and your fences must be one or more closed, non-self-intersecting, and mutually non-intersecting curves such that each canyon is completely within one of the closed areas formed by these curves.

Fences require resources, and the cost is proportional to the length of the fence. You want to minimize the total resource consumption, so you aim to find the infimum of the total fence length. In other words, you want to find the largest real number $x$ such that there is no plan with a total fence length less than $x$.

Input Format

The first line of the input file contains an integer $n$, representing the number of canyons.

The next $n$ lines, the $i$-th line contains four integers $a_i, b_i, c_i, d_i$, indicating that the $i$-th canyon is a line segment connecting points $(a_i, b_i)$ and $(c_i, d_i)$. It is guaranteed that the two endpoints do not coincide, different segments do not involve the same points, and no three points are collinear.

Output Format

Output a single real number, representing the infimum of the total fence length. The absolute or relative error of your answer must not exceed $10^{-6}$.

Sample Input and Output

Sample Input #1

1
0 0 0 1

Sample Output #1

2.00000000

Sample Input #2

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

Sample Output #2

23.563573998194637061425470524757

Sample Input #3

4
-1 1 -1 3
0 4 2 4
3 1 3 3
0 0 2 0

Sample Output #3

13.656854249492380195206754896839

Notes

Sample 1 Explanation

A rectangle with vertices at $(-0.01, -0.01), (-0.01, 1.01), (0.01, 1.01), (0.01, -0.01)$ completely contains the input segment, with a total length of $2.08$, slightly greater than the infimum.

We can prove that there is no plan with exactly a length of $2$. We can construct a plan with any length greater than $2$ by infinitely "tightening" the square towards the input segment.

Sample 2 Explanation

The input segments are shown below, note that the segments can intersect:

We can construct a plan with any total length greater than the answer by infinitely "approaching" these red curves. Note that, from Sample 1, we know that the red segment in the upper left corner is counted twice.

Sample 3 Explanation

The answer is $8 + 4\sqrt{2}$.

Explanation is shown below:

We can construct a plan with any total length greater than $8 + 4\sqrt{2}$ by infinitely "approaching" these red curves.

Test Data Constraints

For $5\%$ of the data, $1 \le n \le 1$.

For $10\%$ of the data, $1 \le n \le 2$.

For $15\%$ of the data, $1 \le n \le 10$.

For $30\%$ of the data, $1 \le n \le 15$.

For $45\%$ of the data, $1 \le n \le 30$.

For $55\%$ of the data, $1 \le n \le 60$.

For $65\%$ of the data, $1 \le n \le 120$.

For $75\%$ of the data, $1 \le n \le 200$.

For an additional $10\%$ of the data, the answer contains at most two curves.

For $100\%$ of the data, $1 \le n \le 250$, $0 \le |a_i|, |b_i|, |c_i|, |d_i| \le 10^9$. It is guaranteed that the two endpoints do not coincide, different segments do not involve the same points, and no three points are collinear.

见题面 Input 部分

见题面 Output 部分