分数: 625 点
问题陈述
有 N 坐标平面中的线段,以及 i第线段 (1\leq i\leq 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)
- 的 i-th 和 j第条线段不共享点 (1\leq i\lt j\leq N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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}.
示例输入 1
4 2 3 2 10 4 0 12 6 4 8 6 3 7 8 10 8
示例输出 1
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 也将被认为是正确的。
示例输入 2
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
示例输出 2
12.875165712523887403637822024952
如图所示的闭合圆盘,中心位于 \left(\dfrac{19817-8\sqrt{5991922}}{18},\dfrac{-2305+\sqrt{5991922}}9\right) 半径为 \dfrac{3757\sqrt{29}-44\sqrt{206618}}{18},与所有线段共享一个点。

示例输入 3
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
示例输出 3
485.264732620930836460637042310401