ABC016 D - 一刀両断
解法
分割される部分が1つ増えるには、線分ABと交差する多角形の辺が2本増える必要があります。
交差する多角形の辺が奇数になることは必ず存在しないので、多角形の辺と交差する辺の本数を2で割り、最後に1追加したものが答えとなります。
今回、問題の条件より、多角形の座標は反時計回りに与えられるため、番目と番目の座標からなる線分が多角形の辺そのものになります。ので、1重ループで交差判定を行っていけば良いです。
交差判定は、何か方法がありそう!と思い検索をかけるとヒットしたのでそれをパクり参考にしました。
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/Intersection.htm
頭良いですねこれ…
ということで、これをそのまま適用して交差判定を行えば、答えを求めることができます。