多くの人の頭(もちろんこれを書いてる人の頭も)を悩ませる問題ジャンルの一つに、幾何がある。ここでは、幾何を考える際に助けになるような典型をのせる。
なお、多くの幾何のパターンはあり本にほとんど網羅されてるので、そちらをご覧になれば幸せになります。
なお、多くの幾何のパターンはあり本にほとんど網羅されてるので、そちらをご覧になれば幸せになります。
包含の判定
幾何の難しいところとしては、数学特有の無限の可能性を持ちうるという事が挙げられる。そのままでは全探索することもままならないのである。二分探索でうまく行く場合はいいが、そうなるのは少数である。
包含の判定では、包含判定する図形の中心座標が無限に有り得て、探索はままならない。
しかし、こういう時は、ギリギリを攻めるのが幾何の常套手段。
ギリギリを攻めるにあたっては、微小変量ずらして、変動するものに注目するのがわかりやすい。こういう変動するものは、大体制約が他より厳しいものである。
包含の判定では、包含判定する図形の中心座標が無限に有り得て、探索はままならない。
しかし、こういう時は、ギリギリを攻めるのが幾何の常套手段。
ギリギリを攻めるにあたっては、微小変量ずらして、変動するものに注目するのがわかりやすい。こういう変動するものは、大体制約が他より厳しいものである。
AOJ1132 Circle and Points
この問題での微小変量をずらすと、
1. 内部の点は変動しない。
2. 辺の上の点は変化する。
2. 辺の上の点は変化する。
ということで、辺の上にのってる点がキーポイントだとわかる。(少しずらしても包含される点に関しては、点の中心を微調整しても問題ないけど、辺の上に乗るという条件は少しずらしてもダメで、より厳しい。)
辺の上に1点を載せることは絶対にできるが、2点を載せることは物によって可能かどうか分かれる。3点以上は、たまたま乗っかった他はありえない。つまり、3点以上が辺上にあるのは2点が辺上にある場合を全探索すればカバーができる。
以上の事実から、2点が載るような中心を全探索すれば、辺の上のその中で最大の包含数がわかる。
辺の上に1点を載せることは絶対にできるが、2点を載せることは物によって可能かどうか分かれる。3点以上は、たまたま乗っかった他はありえない。つまり、3点以上が辺上にあるのは2点が辺上にある場合を全探索すればカバーができる。
以上の事実から、2点が載るような中心を全探索すれば、辺の上のその中で最大の包含数がわかる。