包含の幾何 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

多くの人の頭（もちろんこれを書いてる人の頭も）を悩ませる問題ジャンルの一つに、幾何がある。ここでは、幾何を考える際に助けになるような典型をのせる。
なお、多くの幾何のパターンはあり本にほとんど網羅されてるので、そちらをご覧になれば幸せになります。

包含の判定

幾何の難しいところとしては、数学特有の無限の可能性を持ちうるという事が挙げられる。そのままでは全探索することもままならないのである。二分探索でうまく行く場合はいいが、そうなるのは少数である。
包含の判定では、包含判定する図形の中心座標が無限に有り得て、探索はままならない。
しかし、こういう時は、ギリギリを攻めるのが幾何の常套手段。
ギリギリを攻めるにあたっては、微小変量ずらして、変動するものに注目するのがわかりやすい。こういう変動するものは、大体制約が他より厳しいものである。

AOJ1132 Circle and Points

https://onlinejudge.u-aizu.ac.jp/problems/1132

この問題での微小変量をずらすと、

1. 内部の点は変動しない。
2. 辺の上の点は変化する。

ということで、辺の上にのってる点がキーポイントだとわかる。（少しずらしても包含される点に関しては、点の中心を微調整しても問題ないけど、辺の上に乗るという条件は少しずらしてもダメで、より厳しい。）
辺の上に1点を載せることは絶対にできるが、2点を載せることは物によって可能かどうか分かれる。3点以上は、たまたま乗っかった他はありえない。つまり、3点以上が辺上にあるのは2点が辺上にある場合を全探索すればカバーができる。
以上の事実から、2点が載るような中心を全探索すれば、辺の上のその中で最大の包含数がわかる。