B - Holes (agc021_b) ギフト包装法 (convex)

Quiz

https://atcoder.jp/contests/agc021/tasks/agc021_b

Submit

https://atcoder.jp/contests/agc021/submissions/3933490

Step 1

  • Rを無限大に持っていくと凸包内の点などの確率が0になる
  • 凸包を求めて垂直二等分線の角度が2πのうちのどれだけを占めるかが確率となる
    • とはいえ垂直二等分線を求めるのは面倒
    • 点の角度で考えてよい

Step 2

  • こうして解けることに気づけたとして、凸包を求める必要がある
  • アルゴリズムは複数ある
  • 例外対応として、N=2や、N=3以上でも直線上に並んでいる場合を考慮する

凸包の作成のためのGift Wrapping Algorithm

  • 効率的ではないが実装が楽
  • はまりポイント
    • 参考にした実装内の orientation 内にintが存在
    • 今回のテストケースではかけ算したときにあふれ、whileが止まらなくなった...

内角の和は180度

  • 凸包内の3点を考える
  • 垂直二等分線の交点と、垂直二等分線からなる角度を求めたい
  • 交点求めて・・・ってするの面倒そう
  • よく見ると、ノートのように4点は円上にある
  • よってベクトルv, wの角度を求めれば、内角の和は180度から求めたい角度も求まる

今後の課題

  • Pointクラスに演算子定義などしたが、2次元の点なのでcomplexを使うと楽かもしれない

Thanks (Gift Wrapping Algorithm)

類題