103147: [Atcoder]ABC314 Ex - Disk and Segments
Description
Score : $625$ points
Problem Statement
There are $N$ line segments in a coordinate plane, and the $i$-th line segment $(1\leq i\leq N)$ has two points $(a _ i,b _ i)$ and $(c _ i,d _ i)$ as its endpoints. Here, each line segment includes its endpoints. Additionally, no two line segments share a point.
We want to place a single closed disk in this plane so that it shares a point with each line segment. In other words, we want to draw a single circle so that each line segment shares a point with either the circumference of the circle or its interior (or both). Find the smallest possible radius of such a disk.
Constraints
- $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)$
- The $i$-th and $j$-th line segments do not share a point $(1\leq i\lt j\leq N)$.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$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$
Output
Print the answer in a single line. Your output will be considered correct when the absolute or relative error from the true value is at most $10 ^ {−5}$.
Sample Input 1
4 2 3 2 10 4 0 12 6 4 8 6 3 7 8 10 8
Sample Output 1
3.319048676309097923796460081961
The given line segments are shown in the figure below. The closed disk shown in the figure, centered at $\left(\dfrac{32-\sqrt{115}}4,\dfrac{21-\sqrt{115}}2\right)$ with a radius of $\dfrac{24-\sqrt{115}}4$, shares a point with all the line segments.
It is impossible to place a disk with a radius less than $\dfrac{24-\sqrt{115}}4$ so that it shares a point with all the line segments, so the answer is $\dfrac{24-\sqrt{115}}4$.
Your output will be considered correct if the absolute or relative error from the true value is at most $10^{-5}$, so outputs such as 3.31908 and 3.31902 would also be considered correct.
Sample Input 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
Sample Output 2
12.875165712523887403637822024952
The closed disk shown in the figure, centered at $\left(\dfrac{19817-8\sqrt{5991922}}{18},\dfrac{-2305+\sqrt{5991922}}9\right)$ with a radius of $\dfrac{3757\sqrt{29}-44\sqrt{206618}}{18}$, shares a point with all the line segments.
Sample Input 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
Sample Output 3
485.264732620930836460637042310401
Input
Output
问题描述
在一个坐标平面上有$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$条和第$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