圆盘与线段

题目描述

坐标平面上有 $N$ 条线段，第 $i$ 条线段（$1 \le i \le N$）以 $(a_i, b_i)$ 和 $(c_i, d_i)$ 两个点为端点。 这里，每条线段都包含其端点。 此外，任意两条线段都没有公共点。

我们想在该平面上放置一个闭圆盘，使其与每条线段都有公共点。 换句话说，我们要画一个圆，使得每条线段与圆周或其内部（或两者）都有公共点。 求这样的圆盘的最小可能半径。

输入格式

输入按以下格式从标准输入给出：

$N$
$a_1$ $b_1$ $c_1$ $d_1$
$a_2$ $b_2$ $c_2$ $d_2$
$\vdots$
$a_N$ $b_N$ $c_N$ $d_N$

输出格式

在一行内输出答案。当输出与真实值的绝对误差或相对误差不超过 $10^{-5}$ 时判为正确。

样例

4
2 3 2 10
4 0 12 6
4 8 6 3
7 8 10 8

3.319048676309097923796460081961

给定的线段如下图所示。 图中所示的闭圆盘，圆心为 $\left(\dfrac{32-\sqrt{115}}4, \dfrac{21-\sqrt{115}}2\right)$，半径为 $\dfrac{24-\sqrt{115}}4$，与所有线段都有公共点。

不可能存在半径小于 $\dfrac{24-\sqrt{115}}4$ 的圆盘与所有线段都有公共点，因此答案为 $\dfrac{24-\sqrt{115}}4$。

当输出与真实值的绝对误差或相对误差不超过 $10^{-5}$ 时判为正确，因此输出 3.31908 或 3.31902 也会被判为正确。

20
0 18 4 28
2 21 8 21
3 4 10 5
3 14 10 13
5 9 10 12
6 9 10 6
6 28 10 18
12 11 15 13
12 17 12 27
13 17 20 18
13 27 19 26
16 1 16 13
16 22 19 25
17 22 20 19
18 4 23 4
18 5 23 11
22 16 22 23
23 15 30 15
23 24 30 24
24 0 24 11

12.875165712523887403637822024952

图中所示的闭圆盘，圆心为 $\left(\dfrac{19817-8\sqrt{5991922}}{18}, \dfrac{-2305+\sqrt{5991922}}9\right)$，半径为 $\dfrac{3757\sqrt{29}-44\sqrt{206618}}{18}$，与所有线段都有公共点。

30
526 655 528 593
628 328 957 211
480 758 680 794
940 822 657 949
127 23 250 385
281 406 319 305
277 598 190 439
437 450 725 254
970 478 369 466
421 225 348 141
872 64 600 9
634 460 759 337
878 514 447 534
142 237 191 269
983 34 554 284
694 160 589 239
391 631 22 743
377 656 500 606
390 576 184 312
556 707 457 699
796 870 186 773
12 803 505 586
343 541 42 165
478 340 176 2
39 618 6 651
753 883 47 833
551 593 873 672
983 729 338 747
721 77 541 255
0 32 98 597

485.264732620930836460637042310401

数据范围

• $2 \le N \le 100$
• $0 \le a_i, b_i, c_i, d_i \le 1000$（$1 \le i \le N$）
• $(a_i, b_i) \neq (c_i, d_i)$（$1 \le i \le N$）
• 第 $i$ 条线段和第 $j$ 条线段没有公共点（$1 \le i \lt j \le N$）。
• 输入均为整数。