昨夜、あなたが走っているのを見た

恵みに満ちた広々とした野原で

あなたはもう傷ついても、苦しんでもいなかった[^1]

あなたは見渡す限りの広大な野原を見つけました。この野原では、かつて傷つき、苦しんだ過去を忘れています。あなたは神の恵みの中を子供のように走り回ります。

しかし、一つ問題に気づきました。この野原にはいくつかの峡谷があり、いつ峡谷に落ちてもおかしくありません。自由に走り続けるため、あなたはいくつかの柵でこれらの峡谷を囲むことにしました。

峡谷の幅は無視し、それぞれの峡谷を線分とみなせます。これらの線分は交差してもかまいません。柵は、自己交差せず、互いにも交差しない、1 本以上の閉曲線でなければならず、どの峡谷も、いずれか一つの閉曲線が囲む閉領域に完全に含まれるようにする必要があります。

もちろん、柵には資源が必要で、消費する資源は柵の長さに比例します。資源の総消費量を最小にしたいので、柵の総延長の下限を求めてください。言い換えると、柵の総延長が $x$ より短くなる配置が存在しないような、最大の実数 $x$ を求めてください。

入力

ファイル fields.in からデータを読み込みます。

入力ファイルの最初の行には、峡谷の個数を表す整数 $n$ が与えられます。

続く $n$ 行のうち、$i$ 行目には四つの整数 $a_i,b_i,c_i,d_i$ が与えられます。第 $i$ の峡谷は、点 $(a_i,b_i)$ と点 $(c_i,d_i)$ を結ぶ線分です。二つの端点は一致せず、異なる線分が同じ端点を共有することはありません。また、どの 3 点も同一直線上にないことが保証されます。

出力

ファイル fields.out に出力します。

柵の総延長の下限を表す実数を 1 行に一つ出力してください。あなたの答えと正解の絶対誤差と相対誤差の小さい方が $10^{-6}$ 以下でなければなりません。

入出力例

入力 1

1
0 0 0 1

出力 1

2.00000000

注記

四つの頂点がそれぞれ $(-0.01,-0.01),(-0.01,1.01),(0.01,1.01),(0.01,-0.01)$ である長方形は、入力の線分を完全に含み、総延長は $2.08$ で、下限よりわずかに大きくなります。

長さがちょうど $2$ の配置が存在しないことは証明できます。正方形を入力の線分に向かって限りなく「縮める」ことで、長さが $2$ より大きい任意の値となる配置を作れます。

入力 2

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

出力 2

23.563573998194637061425470524757

注記

次の図は入力の線分です。線分は交差してもよいことに注意してください。

図 1：入出力例 2 の説明

これらの赤い曲線に限りなく「近づける」ことで、総延長が答えより大きい任意の値となる配置を作れます。入出力例 1 から容易に分かるように、左上の赤い線分は 2 回数えられていることに注意してください。

入力 3

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

出力 3

13.656854249492380195206754896839

注記

答えは $8+4\sqrt{2}$ です。

説明を図に示します。

図 2：入出力例 3 の説明

これらの赤い曲線に限りなく「近づける」ことで、総延長が $8+4\sqrt{2}$ より大きい任意の値となる配置を作れます。

入出力例 4

選手用ディレクトリの fields/fields4.in と fields/fields4.ans を参照してください。

制約

$5\%$ のデータでは、$1\le n\le1$ が保証されます。

$10\%$ のデータでは、$1\le n\le2$ が保証されます。

$15\%$ のデータでは、$1\le n\le10$ が保証されます。

$30\%$ のデータでは、$1\le n\le15$ が保証されます。

$45\%$ のデータでは、$1\le n\le30$ が保証されます。

$55\%$ のデータでは、$1\le n\le60$ が保証されます。

$65\%$ のデータでは、$1\le n\le120$ が保証されます。

$75\%$ のデータでは、$1\le n\le200$ が保証されます。

別の $10\%$ のデータでは、答えに含まれる曲線が高々 2 本であることが保証されます。

$100\%$ のデータでは、$1\le n\le250$、$0\le|a_i|,|b_i|,|c_i|,|d_i|\le10^9$ が保証されます。二つの端点は一致せず、異なる線分が同じ端点を共有することはありません。また、どの 3 点も同一直線上にないことが保証されます。

[^1]: 問題文中の歌詞は Jackie Evancho の Open Fields of Grace より引用したもので、作曲者は Lisa Venkatrathnam と Paul Sumares です。