きままにものづくり

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

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: 要素数

コード