問題 F ボ〜ル

問題文

2 次元平面上の原点にボールがあり，x 軸の正方向との角度が反時計回りに見て 0 度 180 度までの間の方向に一様な確率で発射されようとしている (発射される方向は整数角であるとは限らない)．ボールの大きさは十分小さく，平面上では点であると見なすことにする．この問題における目的は，このボールをできるだけ高い確率で捕獲することである．

平面上に N 個の場所 (x_i, y_i) が与えられる．ボールを捕獲するために，あなたは N 個の場所から K 個の場所を選んで，それぞれの場所に人を配置することができる．人は i 番目の与えられた場所に対して半径 r_i 以内の距離まで動いてボールを取ることが出来る．

人の配置をうまく選んでボールを捕獲できる確率を最大にするとき，その確率を出力せよ．

入力形式

入力は以下の形式で与えられる．

N K
x1 y1 r1
...
xN yN rN

出力形式

確率を小数表記で 1 行に出力せよ．小数点以下何桁でも出力して構わないが，相対誤差あるいは絶対誤差が 10^-6 未満になっていなければならない．

制約

• 1≤ N≤ 1,500, 1≤ K≤ N
• |x_i| ≤ 1,000, |y_i| ≤ 1,000, 1 ≤ r_i < (x_i² + y_i²)^1/2
• 入力値はすべて整数である．

入出力例

入力例 1

2 1
10 10 10
-10 10 10

出力例 1

0.50

2 つ場所があり，そのうちのどちらかに人を配置できる．この場合，どちらに配置しても確率は 1/2 になる．

入力例 2

2 2
10 10 10
-10 10 10

出力例 2

1.0

入力例 3

5 3
-10 -10 5
10 10 2
-10 10 3
-10 0 4
10 0 2

出力例 3

0.3574057314330

入力例 4

4 2
1 1 1
2 2 2
3 3 3
4 4 4

出力例 4

0.50