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 statement are from Jackie Evancho's Open Fields of Grace, composed by Lisa Venkatrathnam and Paul Sumares.

You found an endless open field. In this field, you forget the broken and painful past. You run like a child in God's grace.

However, you notice a problem: there are several canyons in this field. At any time, you might fall into a canyon. To keep running freely, you decide to build some fences to enclose these canyons.

We can ignore the width of a canyon and treat each canyon as a line segment. These segments may intersect, and your fences must be one or more closed curves that are non-self-intersecting and pairwise disjoint, such that every canyon lies completely inside the closed region enclosed by some closed curve.

Of course, fences consume resources, and the resource cost is proportional to the total fence length. You want to minimize the total resource cost, so you need 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 whose total fence length is less than $x$.

Input Format

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

The next $n$ lines each contain four integers $a_i,b_i,c_i,d_i$, meaning that the $i$-th canyon is a segment connecting $(a_i,b_i)$ and $(c_i,d_i)$. It is guaranteed that the two endpoints are different, different segments will not use the same point, and no three points are collinear.

Output Format

Output one real number, the infimum of the total fence length. The minimum of the absolute error and the relative error between your answer and the standard answer must not exceed $10^{-6}$.

1
0 0 0 1

2.00000000

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

23.563573998194637061425470524757

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

13.656854249492380195206754896839

Hint

Explanation for Sample 1

A rectangle with four vertices $(−0.01,−0.01),(−0.01,1.01),(0.01,1.01),(0.01,−0.01)$ completely contains the input segment, and its total perimeter is $2.08$, which is slightly larger than the infimum.

We can prove that there is no solution with length exactly $2$. We can construct a solution of any length greater than $2$ by shrinking the square toward the input segment infinitely.

Explanation for Sample 2

The figure below shows the input segments. Note that segments may intersect:

We can construct solutions with any total length greater than the answer by infinitely approaching these red curves. Note that from Sample 1, it is easy to see that the red segment in the upper-left corner is counted twice.

Explanation for Sample 3

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

The explanation is shown in the figure:

We can construct solutions with any total length greater than $8+4\sqrt 2$ by infinitely approaching these red curves.

Testdata Constraints

For $5\%$ of the testdata, it is guaranteed that $1\le n\le 1$.

For $10\%$ of the testdata, it is guaranteed that $1\le n\le 2$.

For $15\%$ of the testdata, it is guaranteed that $1\le n\le 10$.

For $30\%$ of the testdata, it is guaranteed that $1\le n\le 15$.

For $45\%$ of the testdata, it is guaranteed that $1\le n\le 30$.

For $55\%$ of the testdata, it is guaranteed that $1\le n\le 60$.

For $65\%$ of the testdata, it is guaranteed that $1\le n\le 120$.

For $75\%$ of the testdata, it is guaranteed that $1\le n\le 200$.

For another $10\%$ of the testdata, it is guaranteed that the answer contains at most two curves.

For $100\%$ of the testdata, it is guaranteed that $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 are different, different segments will not use the same point, and no three points are collinear.

Translated by ChatGPT 5