[ABC314Ex] Disk and Segments

在平面直角坐标系中，有 $N$ 条线段，第 $i$ 条的端点是 $(a_i,b_i)$ 和 $(c_i,d_i)$，任意线段不共点。 你要在平面上画一个圆，使得任意一条线段都和圆周或圆内部有至少一个公共点，求满足条件的圆的最小半径，绝对或相对误差不超过 $10^{-5}$。 ### 输入格式 第一行一个整数 $N$，接着 $N$ 行每行四个整数 $a_i,b_i,c_i,d_i$。 ### 输出格式 一行一个实数表示答案。 ### 数据范围 * $2\leq N\leq 100$ * $0\leq a_i,b_i, c_i,d_i\leq1000\ (1\leq i\leq N)$ * $(a_i,b_i)\neq(c_i,d_i)\ (1\leq i\leq N)$

[problemUrl]: https://atcoder.jp/contests/abc314/tasks/abc314_h 座標平面上に $ N $ 本の線分があり、$ i $ 本目 $ (1\leq\ i\leq\ N) $ の線分は $ 2 $ 点 $ (a\ _\ i,b\ _\ i),(c\ _\ i,d\ _\ i) $ を端点とする線分です。 ここで、どの線分も端点を含みます。 また、どの $ 2 $ 線分も互いに共有点を持ちません。 この平面上に $ 1 $ つだけ閉円盤を配置し、どの線分とも共有点を持つようにしたいです。 つまり、円を $ 1 $ つ描くことで、どの線分もその円周もしくはその内部（あるいはその両方）と共有点を持つようにしたいです。 そのような円盤の半径としてありえる最小の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

答えを $ 1 $ 行で出力せよ。出力された値と真の値の相対誤差もしくは絶対誤差が $ 10\ ^\ {−5} $ 以下のとき、正答と判定される。

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

3.319048676309097923796460081961

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

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\leq\ N\leq\ 100 $ - $ 0\leq\ a\ _\ i,b\ _\ i,c\ _\ i,d\ _\ i\leq1000\ (1\leq\ i\leq\ N) $ - $ (a\ _\ i,b\ _\ i)\neq(c\ _\ i,d\ _\ i)\ (1\leq\ i\leq\ N) $ - $ i $ 番目の線分と $ j $ 番目の線分の共有点は存在しない $ (1\leq\ i\lt\ j\leq\ N) $ - 入力はすべて整数 ### Sample Explanation 1 与えられた線分は以下の図のようになります。 図のように、中心が $ \left(\dfrac{32-\sqrt{115}}4,\dfrac{21-\sqrt{115}}2\right) $ で半径が $ \dfrac{24-\sqrt{115}}4 $ である閉円盤はすべての線分と共通点を持ちます。 !\[\](https://img.atcoder.jp/abc314/cbcd8322e610eefca04d6f5a7ddbc89a.png) 半径が $ \dfrac{24-\sqrt{115}}4 $ 未満の円盤をどう配置しても、すべての線分と共有点を持つようにすることはできないため、答えは $ \dfrac{24-\sqrt{115}}4 $ です。 出力と真の値との絶対誤差もしくは相対誤差が $ 10^{-5} $ 以下であれば正答と判定されるため、`3.31908` や `3.31902` などと出力しても正解になります。 ### Sample Explanation 2 図のように、中心が $ \left(\dfrac{19817-8\sqrt{5991922}}{18},\dfrac{-2305+\sqrt{5991922}}9\right) $ で半径が $ \dfrac{3757\sqrt{29}-44\sqrt{206618}}{18} $ である閉円盤はすべての線分と共通点を持ちます。 !\[\](https://img.atcoder.jp/abc314/6f259a531d06b430c5dc1299c4d2ecdd.png)