2 次元平面上の原点にボールがあり,x 軸の正方向との角度が反時計回りに見て 0 度 180 度までの間の方向に一様な確率で発射されようとしている (発射される方向は整数角であるとは限らない).ボールの大きさは十分小さく,平面上では点であると見なすことにする.この問題における目的は,このボールをできるだけ高い確率で捕獲することである.
平面上に N 個の場所 (xi, yi) が与えられる.ボールを捕獲するために,あなたは N 個の場所から K 個の場所を選んで,それぞれの場所に人を配置することができる.人は i 番目の与えられた場所に対して半径 ri 以内の距離まで動いてボールを取ることが出来る.
人の配置をうまく選んでボールを捕獲できる確率を最大にするとき,その確率を出力せよ.
入力は以下の形式で与えられる.
N K x1 y1 r1 ... xN yN rNN はボールを捕獲するために人を置くための場所の数であり,K はその中から使うことの出来る場所の数である. (xi, yi) は i 番目の場所の座標であり,ri はそこから動くことの出来る距離である.
確率を小数表記で 1 行に出力せよ.小数点以下何桁でも出力して構わないが,相対誤差あるいは絶対誤差が 10-6 未満になっていなければならない.
2 1 10 10 10 -10 10 10
0.50
2 つ場所があり,そのうちのどちらかに人を配置できる.この場合,どちらに配置しても確率は 1/2 になる.
2 2 10 10 10 -10 10 10
1.0
5 3 -10 -10 5 10 10 2 -10 10 3 -10 0 4 10 0 2
0.3574057314330
4 2 1 1 1 2 2 2 3 3 3 4 4 4
0.50