B - Emblem

Time Limit: 1 sec / Memory Limit: 256 MB

配点:300

問題文

E869120 君は, square869120Contest #5 の開催を記念するために, 1, 2, 3, \cdots, N+M の番号がつけられた N + M 個の円を用いて 2 次元平面上にエンブレムを作ろうとしている.
番号 1, 2, 3, \cdots, N の円は, 中心座標 (x_i, y_i) と半径 r_i が決まっている.
その一方で, 番号 N+1, N+2, N+3, \cdots, N+M の円は, 中心座標 (x_i, y_i) が決まっているが, 半径は決まっていない.
エンブレムに使われる円は接してもよいが, どの円も他の円と交わるまたは含んではならないとき, 最も小さい円の半径を最大化しなさい.

入力

入力は以下の形式で標準入力から与えられる.

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}

出力

最も小さい円の半径としてありうる最大値を, 1 行で出力しなさい.
ただし, 相対誤差または絶対誤差が 10^{-6} 以内であるとき正解とみなされる.


制約

  • N0 以上 100 以下の整数.
  • M0 以上 100 以下の整数.
  • N + M \geq 2.
  • x_i, y_i \ (1 \leq i \leq N+M)-100 以上 100 以下の整数.
  • r_i1 以上 100 以下の整数.
  • 入力で与えられる座標はすべて異なる.
  • 番号 1, 2, 3, \cdots, N の円は交差せず, ある円がほかの円を含まない.
  • 番号 N+1, N+2, N+3, \cdots, N+M の円は, 番号 1, 2, 3, \cdots, N の円の内部または円周上にない.

小課題

小課題 1 [70 点]

  • N = 0.
  • M = 2.

小課題 2 [140 点]

  • N = 0.

小課題 3 [90 点]

  • 追加の制約はない.

入力例 1

0 2
6 3
2 4

出力例 1

2.061552812808830

この場合, 円の半径を 2 つとも \frac{\sqrt{17}}{2} に設定すれば, 2 つの円は接し, 最小の円の半径が \frac{\sqrt{17}}{2} = 2.06155\cdots になる.
例えば, 以下の図のようなエンブレムができる.


入力例 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

この場合, 半径が自由に設定できる円はありません. よって, 最小の円の半径は 3 つの円の半径のうち最小である 2 になる.


入力例 4

1 1
0 0 5
6 -3

出力例 4

1.708203932499369

このとき, 番号 2 の円の半径を 3 \sqrt{5} - 5 に設定すれば, 最小の円の半径は 3 \sqrt{5} - 5 = 1.70820 \cdots になる.
例えば, 以下の図のようなエンブレムができる.

Max Score:300 points

Problem Statement

E869120 the coder is going to create an emblem which is consist of N+M circles conveniently numbered 1, 2, 3, \cdots, N+M, to celebrate the holding of "square869120Contest #5".
He has already decided the center point (x_i, y_i) and radius r_i, for circle i \ (1 \leq i \leq N).
He has also decided the center point (x_i, y_i) for circle i (N+1 \leq i \leq N+M), but he hasn't decided the radius of these circles.
Circle can contact with other circles, but no circle can intersect to or enclose any other circles.
Please maximize the radius of the smallest circle in the emblem.

Input

Input is given from Standard Input in the following format:

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}

Output

Print the maximum value of "the radius of the smallest circle".
The output will be judged correct when the absolute or relative error is at most 10^{-6}.


Constraints

  • N is an integer between 0 and 100 (inclusive).
  • M is an integer between 0 and 100 (inclusive).
  • N + M \geq 2.
  • x_i, y_i \ (1 \leq i \leq N+M) are integers between -100 and 100 (inclusive).
  • r_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive).
  • No pair of circle's center point are equal.
  • Circle which the radius has been decided neither intersect to nor enclose the other circle which the radius has been decided.
  • No center point of the circle whose the radius has not been decided is in or on a circle which the radius has been decided.

Subtasks

Subtask 1 [70 points]

  • N = 0.
  • M = 2.

Subtask 2 [140 points]

  • N = 0.

Subtask 3 [90 points]

  • There are no additional constraints.

Sample Input 1

0 2
6 3
2 4

Sample Output 1

2.061552812808830

In this case, if you set the radius of circle 1, 2 to \frac{\sqrt{17}}{2}, the two circles contacts, and the radius of the smallest circle will be maximized.
An example of emblem is as follows:


Sample Input 2

0 5
8 6
9 1
2 0
1 0
0 1

Sample Output 2

0.500000000000000

An example of emblem is as follows:


Sample Input 3

3 0
5 2 3
-1 0 2
2 -6 4

Sample Output 3

2.000000000000000

In this case, there is no circle which the radius has not been decided. So, obviously, the radius of the smallest circle is always 2.


Sample Input 4

1 1
0 0 5
6 -3

Sample Output 4

1.708203932499369

In this case, you can maximize the radius of smallest circle if you set the radius of circle 2 to 3 \sqrt{5} - 5.
An example of emblem is as follows: