最高分数:300 点
问题陈述
E869120 编码器将创建一个标志,其中包含 N+M 圆圈方便编号 1, 2, 3, \cdots, N+M,庆祝“square869120Contest #5”的举行。
他已经决定了中心点 (x_i, y_i) 和半径 r_i,对于圆 i \ (1 \leq i \leq N).
他也决定了中心点 (x_i, y_i) 为圆 i (N+1 \leq i \leq N+M),但他还没有确定这些圆的半径。
圆可以与其他圆接触,但任何圆都不能与任何其他圆相交或包围。
请将徽章中最小圆圈的半径最大化。
输入
输入由标准输入按以下格式给出:
N M
x_1 y_1 r_1
x_2 y_2 r_2
: :
x_N y_N r_N
x_{N+1} y_{N+1}
x_{N+2} y_{N+2}
: :
x_{N+M} y_{N+M}
输出
打印“最小圆的半径”的最大值。
当绝对或相对误差最大时判断输出正确 10^{-6}.
约束
- N 是介于 0 和 100 (含)。
- M 是介于 0 和 100 (含)。
- N + M \geq 2.
- x_i, y_i \ (1 \leq i \leq N+M) 是介于 -100 和 100 (含)。
- r_i \ (1 \leq i \leq N) 是介于 1 和 100 (含)。
- 没有一对圆的中心点是相等的。
- 半径已确定的圆既不与另一个半径已确定的圆相交也不包围。
- 半径尚未确定的圆的中心点不在半径已确定的圆内或之上。
子任务
子任务 1 [70 点]
- N = 0.
- M = 2.
子任务 2 [140 点]
- N = 0.
子任务 3 [90 点]
- 没有其他限制。
示例输入 1
0 2 6 3 2 4
示例输出 1
2.061552812808830
在这种情况下,如果设置圆的半径 1, 2 to \frac{\sqrt{17}}{2},两个圆接触,最小圆的半径将最大化。
标志示例如下:
示例输入 2
0 5 8 6 9 1 2 0 1 0 0 1
示例输出 2
0.500000000000000
标志示例如下:
示例输入 3
3 0 5 2 3 -1 0 2 2 -6 4
示例输出 3
2.000000000000000
在这种情况下,不存在半径尚未确定的圆。所以,显然,最小圆的半径总是 2.
示例输入 4
1 1 0 0 5 6 -3
示例输出 4
1.708203932499369
在这种情况下,如果设置圆的半径,则可以最大化最小圆的半径 2 to 3 \sqrt{5} - 5.
标志示例如下: