← 返回题目列表

AtCoder · abc314_h

Ex. 磁盘和段

中文机器翻译题面 查看原题

分数: 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