2014-11-01 SRM621Div1Easy 問題 平面の上に中心点が、半径がの円がN個存在する。平面の中心(0,0)から半径rの円を新しく描く。rは[0,Z]の中からランダムに選ばれる。この時、新しく描く円が既に存在するそれぞれの円と全く被らないか、全て被る場合は良い円とする。逆に、一部だけ被ってしまう円を悪い円とする。良い円が描ける確立を求めよ。 解法 各円の平面の中心までの最近距離と最遠距離は、円の中心点と平面の中心の距離をdとすると となる。 との間でrが選ばれると悪い円となる。重複箇所に注意して、この区間の総和を計算すると、答えが求まる。 計算量 N: 要素数 コード
、半径が
の円がN個存在する。平面の中心(0,0)から半径rの円を新しく描く。rは[0,Z]の中からランダムに選ばれる。この時、新しく描く円が既に存在するそれぞれの円と全く被らないか、全て被る場合は良い円とする。逆に、一部だけ被ってしまう円を悪い円とする。良い円が描ける確立を求めよ。