AOJ : 2256 Divide the Cake ケーキ分割問題

Divide the Cake | Aizu Online Judge

問題概要

  •  W*Hの平面にN個の点があります。
  • 左端から右端に線分を一本ランダムに配置したとき点を半々に分割できる確率はいくつか

解法

  • 二点を選んで線分を引き丁度半分に分割できた時その線分は入れ替わりのイベント線分(?)になる。
  • 四隅とある点を結ぶ線分についても同様に列挙する。
  • 各区間についてみてみるとこうなる。f:id:satelliteyezu:20160508150327g:plain
  • ある赤い区間について右の黄色い区間の長さの変異は1次関数になっている。
  • なので赤い区間の中心につて黄色い区間の長さを求めると平均がとれるのでそれを赤い区間の長さでかければよい。
  • 各区間について足し合わせたものを H*H で割る。
ソースコード

感想

むずかしい。

VA中は頑張って積分しようかと思ったけど各処理について自信が無くてずっとバグってた。

1次関数になるから真ん中とればいいというのは気付けなかったけど面白い。