/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
座標平面上に N 本の線分があり、i 本目 (1\leq i\leq N) の線分は 2 点 (a _ i,b _ i),(c _ i,d _ i) を端点とする線分です。 ここで、どの線分も端点を含みます。 また、どの 2 線分も互いに共有点を持ちません。
この平面上に 1 つだけ閉円盤を配置し、どの線分とも共有点を持つようにしたいです。 つまり、円を 1 つ描くことで、どの線分もその円周もしくはその内部（あるいはその両方）と共有点を持つようにしたいです。 そのような円盤の半径としてありえる最小の値を求めてください。
制約
- 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
出力
答えを 1 行で出力せよ。出力された値と真の値の相対誤差もしくは絶対誤差が 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
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