← 返回题目列表

AtCoder · s8pc_5_b

B. 徽章

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

最高分数: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.
标志示例如下: