京都大学プログラミングコンテスト2015

K - SOULBLOCK


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 512MB

問題文

あなたは以下のようなゲームを作成した.

  • ゲームフィールドは二次元平面とみなすことができる.プレーヤーは原点に存在する点であり,フィールド上には円形のオブジェクトがいくつか存在する.
  • それぞれのオブジェクトには価値が決められている.
  • オブジェクトは別の物体に衝突されるまで止まったままである.
  • プレーヤーはゲーム開始時に,好きな方向を一度だけ選ぶ.すると,プレーヤーは選んだ方向に直進し続ける.
  • プレーヤーが止まっているオブジェクトにぶつかった時,オブジェクトはプレーヤーと衝突した箇所でくっつき,以降はプレーヤーと同じ方向に動く.
  • 動いているオブジェクトが止まっているオブジェクトにぶつかった時,オブジェクト同士は衝突した箇所でくっつき,以降はプレーヤーと同じ方向に動く.
  • 最終的に,プレーヤーと(直接的、あるいは間接的に)つながっているオブジェクトの価値の総和がプレーヤーのスコアとなる.

あなたはこのゲームを公開していたが、悪意のあるプレーヤーによって改造されてしまい,でたらめな方向にプレーヤーを発射するようになってしまった.
プレーヤーが一様にランダムな方向に飛び出すと仮定した時,プレーヤーが獲得するスコアの期待値を出力せよ.


入力

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

N
X_1 Y_1 R_1 W_1
:
X_N Y_N R_N W_N
  • 1 行目にオブジェクトの数を表す整数 N ( 1 \leq N \leq 2000 ) が与えられる.
  • 続く N 行にオブジェクトの中心座標を表す整数 X_i, Y_i ( -10^4 \leq X_i, Y_i \leq 10^4 ) , 半径を表す整数 R_i ( 1 \leq R_i \leq 10^4 ), 価値を表す整数 W_i ( 1 \leq W_i \leq 10^4 ) が与えられる.
  • ゲーム開始時にはプレーヤーはどのオブジェクトの内部または境界上にも存在しないことが保証される.
  • ゲーム開始時には異なる 2 つのオブジェクトは交差せず,接してもいないことが保証される.

出力

プレーヤーのスコアの期待値を 1 行に出力せよ.
小数点以下何桁でも出力して構わないが,絶対誤差または相対誤差が 10^{-6} 未満になっていなければならない.

部分点

以下の制約を満たすデータセットに全て正解した場合は 30 点の部分点が与えられる.

  • N \leq 100

入力例1

1
2 0 1 1

出力例1

0.166666666666667

入力例2

2
2 0 1 1
10 0 1 10

出力例2

0.970972899218329

入力例3

2
100 0 99 1
47 85 1 1

出力例3

0.584414703195711

Source name

京都大学プログラミングコンテスト2015

Submit提出する