AT_joisc2018_b 柵 (Fences)
题目描述
[English statement](https://www2.ioi-jp.org/camp/2018/2018-sp-tasks/day1/fences-en.pdf)
JOI 君在 IOI 国拥有广阔的土地。
IOI 国的土地可以表示为一个平面直角坐标系。他的土地为坐标系上 $x,y$ 坐标满足 $x \in [-10^{100}\, , \, 10^{100}] \, , \, y \in [-10^{100}\, , \, 10^{100}]$ 的区域。他的牧场是在坐标系上 $x,y$ 满足 $x \in [-S\, , \, S] \, , \, y \in [-S\, , \, S]$ 的区域。
JOI 君要在牧场里修一些栅栏,来把牧场围起来,使得他的牛不可能从牧场内的任何一点走到他的土地之外。栅栏是一条长度为正实数的线段。牧场里已经有一些栅栏了。两个栅栏之间如果有共同点,那么它必然是至少一个的栅栏的端点。
JOI 君可以随意建栅栏。要求栅栏既不在牧场内,也不在 JOI 君的土地外,它们的长度任意,方向任意。他甚至可以修一条将整个牧场全围起来的栅栏。建造一条长度为 $l$ 的栅栏的费用是 $l$。两条栅栏可以相交,重合...... 怎么修都没问题(可参考样例)。
请你计算修栅栏的最小费用。
输入格式
第一行为整数 $N$ 和 $S$。
第 $i$ 行 $(1\le i \le N)$ 为四个整数 $A_i,B_i,C_i,D_i$ ,代表有一条连接点 $(A_i,B_i)$ 和点 $(C_i,D_i)$ 的栅栏。
输出格式
输出修栅栏的最小费用。
我们将会使用 SPJ。被允许的最大精度误差为 $0.01$。
说明/提示
全部的输入数据满足以下条件:
$1\le N\le 100$。
$1\le S\le 200$。
$-200\le A_{i}\le 200 (1\le i\le N)$。
$-200\le B_{i}\le 200 (1\le i\le N)$。
$-200\le C_{i}\le 200 (1\le i\le N)$。
$-200\le D_{i}\le 200 (1\le i\le N)$。
子任务:
Subtask 1(18 分):$N=1$。
Subtask 2(33 分):$N\le 6$。
Subtask 3(49 分):没有额外限制。