Ball

Time Limit : 1 sec, Memory Limit : 65536 KB

問題 F ボ〜ル

問題文

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

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

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

入力形式

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

N K
x1 y1 r1
...
xN yN rN
N はボールを捕獲するために人を置くための場所の数であり,K はその中から使うことの出来る場所の数である. (xi, yi)i 番目の場所の座標であり,ri はそこから動くことの出来る距離である.

出力形式

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

制約

  • 1≤ N≤ 1,500, 1≤ K≤ N
  • |xi| ≤ 1,000, |yi| ≤ 1,000, 1 ≤ ri < (xi2 + yi2)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

Source: Kyoto University Programming Contest 2011 , Kyoto, Japan, 2011-08-06
Problem Setter:  Mitsuru Kusumoto ,  Shingo Mori
http://www.kupc.jp/2011.html