列表

详情


NC53243. 栅栏

描述

译自 JOISC 2018 Day1 T2「 / Fences

JOI君在IOI国拥有广阔的土地。
IOI国的土地可以表示为一个平面直角坐标系。他的土地为坐标系上x,y坐标满足的区域。他的牧场是在坐标系上x,y满足的区域。
JOI君要在牧场里修一些栅栏,来把牧场围起来,使得他的牛不可能从牧场内的任何一点走到栅栏之外。栅栏是一条长度为正实数的线段。牧场里已经有一些栅栏了。两个栅栏之间如果有共同点,那么它必然是至少一个的栅栏的端点。
JOI君可以随意建栅栏。要求栅栏既不在牧场内,也不在JOI君的土地外,它们的长度任意,方向任意。他甚至可以修一条将整个牧场全围起来的栅栏。建造一条长度为l的栅栏的费用是l。两条栅栏可以相交,重合......怎么修都没问题(可参考样例)。
请你计算修栅栏的最小费用。

输入描述

第一行为整数N和S。
第i行为四个整数A_i,B_i,C_i,D_i,代表有一条连接点(A_i,B_i)和点(C_i,D_i)的栅栏。

输出描述

输出修栅栏的最小费用。
我们将会使用SPJ。被允许的最大精度误差为0.01。

示例1

输入:

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

输出:

29.0000000000

说明:

已经建好的栅栏见左图,点线为牧场的边界。
一种修栅栏的方法见右图。如果你输出29或28.999也对。
PIC

示例2

输入:

1 2
-3 -3 -3 -2

输出:

16.0000000000

说明:

你根本用不到之前修好的任何栅栏。

示例3

输入:

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

输出:

14.1392801789

示例4

输入:

10 80
175 95 60 -146
-106 57 18 185
190 -68 177 -142
84 -195 127 -179
34 143 126 69
-92 133 -190 80
-157 -66 -119 -161
-85 -124 129 -171
141 181 175 175
107 -38 150 148

输出:

238.4778364511

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

上一题