A5869. 「CTS2019 | CTSC2019」田野
编程题
NOI/NOI+/CTSC
知识点
题目描述
> Last night I saw you running
In the open fields of grace
No longer were you broken or in pain
>
> 题面中的歌词来自 Jackie Evancho 的 Open Fields of Grace，作曲者为 Lisa Venkatrathnam 和 Paul Sumares。
你找到了一片一望无际的大田野，在这片田野中你忘记了曾经破碎、痛苦的过去。你像小孩一样在上帝的恩赐中奔跑。
然而你发现了一个问题，在这片田野中有若干条峡谷。你随时都有坠入峡谷中的危险。为了继续自由自在的奔跑，你决定用若干围栏将这些峡谷围起来。
我们可以忽视峡谷的宽度，将每一条峡谷看做一条线段。**这些线段可以相交**，而你的围栏必须是**一条或多条闭合不自交且两两不相交的曲线**，使得**任何一个峡谷都完全在某一条**闭合曲线围成的闭合区域之内。
当然，围栏需要消耗资源，消耗的资源和围栏的长度成正比，你希望最小化消耗的资源总量，所以你希望求出围栏总长度的**下确界**，换句话说，你希望找到一个最大的实数 $x$，使得不存在一个方案使得围栏总长度小于 $x$。
In the open fields of grace
No longer were you broken or in pain
>
> 题面中的歌词来自 Jackie Evancho 的 Open Fields of Grace，作曲者为 Lisa Venkatrathnam 和 Paul Sumares。
你找到了一片一望无际的大田野，在这片田野中你忘记了曾经破碎、痛苦的过去。你像小孩一样在上帝的恩赐中奔跑。
然而你发现了一个问题，在这片田野中有若干条峡谷。你随时都有坠入峡谷中的危险。为了继续自由自在的奔跑，你决定用若干围栏将这些峡谷围起来。
我们可以忽视峡谷的宽度，将每一条峡谷看做一条线段。**这些线段可以相交**，而你的围栏必须是**一条或多条闭合不自交且两两不相交的曲线**，使得**任何一个峡谷都完全在某一条**闭合曲线围成的闭合区域之内。
当然，围栏需要消耗资源，消耗的资源和围栏的长度成正比，你希望最小化消耗的资源总量，所以你希望求出围栏总长度的**下确界**，换句话说，你希望找到一个最大的实数 $x$，使得不存在一个方案使得围栏总长度小于 $x$。
输入格式
输入文件的第一行为一个整数 $n$，表示峡谷的个数。
接下来 $n$ 行，第 $i$ 行四个整数 $a_i,b_i,c_i,d_i$，表示第 $i$ 条峡谷为一条连接点 $(a_i,b_i)$ 和点 $(c_i,d_i)$ 的线段。**保证两个端点不重合，不同的线段不会涉及到相同的点。保证任意三点不共线。**
接下来 $n$ 行，第 $i$ 行四个整数 $a_i,b_i,c_i,d_i$，表示第 $i$ 条峡谷为一条连接点 $(a_i,b_i)$ 和点 $(c_i,d_i)$ 的线段。**保证两个端点不重合，不同的线段不会涉及到相同的点。保证任意三点不共线。**
输出格式
输出一行一个实数，表示围栏总长度的下确界。**你的答案和标准答案的绝对误差和相对误差的最小值不能超过** $10^{−6}$。
输入输出样例
输入 #1
1 0 0 0 1
输出 #1
2.00000000
输入 #2
4 -2 7 -1 7 0 0 0 1 2 -3 5 5 1 0 6 -1
输出 #2
23.563573998194637061425470524757
输入 #3
4 -1 1 -1 3 0 4 2 4 3 1 3 3 0 0 2 0
输出 #3
13.656854249492380195206754896839
说明/提示
对于 $5\%$ 的数据，保证 $n = 1$。
对于 $10\%$ 的数据，保证 $1\le n\le 2$。
对于 $15\%$ 的数据，保证 $1\le n\le 10$。
对于 $30\%$ 的数据，保证 $1\le n\le 15$。
对于 $45\%$ 的数据，保证 $1\le n\le 30$。
对于 $55\%$ 的数据，保证 $1\le n\le 60$。
对于 $65\%$ 的数据，保证 $1\le n\le 120$。
对于 $75\%$ 的数据，保证 $1\le n\le 200$。
对于另外 $10\%$ 的数据，保证答案最多包含两条曲线。
对于 $100\%$ 的数据，保证 $1\le n\le 250$，$0\le |a_i|,|b_i|,|c_i|,|d_i|\le 10^9$。
保证两个端点不重合，不同的线段不会涉及到相同的点。保证任意三点不共线。
### UPD 2019.10.5
更新了测试数据 ``
对于 $10\%$ 的数据，保证 $1\le n\le 2$。
对于 $15\%$ 的数据，保证 $1\le n\le 10$。
对于 $30\%$ 的数据，保证 $1\le n\le 15$。
对于 $45\%$ 的数据，保证 $1\le n\le 30$。
对于 $55\%$ 的数据，保证 $1\le n\le 60$。
对于 $65\%$ 的数据，保证 $1\le n\le 120$。
对于 $75\%$ 的数据，保证 $1\le n\le 200$。
对于另外 $10\%$ 的数据，保证答案最多包含两条曲线。
对于 $100\%$ 的数据，保证 $1\le n\le 250$，$0\le |a_i|,|b_i|,|c_i|,|d_i|\le 10^9$。
保证两个端点不重合，不同的线段不会涉及到相同的点。保证任意三点不共线。
### UPD 2019.10.5
更新了测试数据 ``
fields17.in`（`.out`` 不变）和样例 2。已重测。