きままにものづくり

日々の気付いたことなんかを書いてます。

SRM621Div1Easy

問題

平面の上に中心点が (X_i, Y_i)、半径が R_iの円がN個存在する。平面の中心(0,0)から半径rの円を新しく描く。rは[0,Z]の中からランダムに選ばれる。この時、新しく描く円が既に存在するそれぞれの円と全く被らないか、全て被る場合は良い円とする。逆に、一部だけ被ってしまう円を悪い円とする。良い円が描ける確立を求めよ。

解法

各円の平面の中心までの最近距離l_{near}と最遠距離 l_{far}は、円の中心点と平面の中心の距離をdとすると
 l_{near} = max(0, R - d)
 l_{far} = R + d
となる。
l_{near} l_{far}の間でrが選ばれると悪い円となる。重複箇所に注意して、この区間の総和を計算すると、答えが求まる。

計算量

 O(N)
N: 要素数

コード

広告を非表示にする