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)
- https://www.sanfoundry.com/cpp-program-implement-gift-wrapping-algorithm-two-dimensions/
- 計算量O(nh)
- n : vertex num
- h : 凸包の辺の数
- 一般的に遅い
- よりよい方法?→
- Andrew’s Monotone Chain O(n log n)
- https://nicklaw.netlify.com/post/2018/03/02/agc021b/
類題
- AOJ Convex Hull