ABC#16 D.一刀両断

問題

各頂点が整数点の多角形と線分Lが与えられる。
多角形を線分が分断し複数の多角形に分割するとき、分割後の多角形の数を返す。
線分は多角形をちゃんと分割するように与えられる。

考え方

よく考えると(←)、「線分によって分割される切断面の数＋1」が答えになっている。
切断面は両端の交点を2つ含むので、「線分Lと多角形の辺の交点数/2＋1」が答えになる。
なので、線分Lと各辺の交点数を求めればよい。

メモ

多角形なので、切断面がある場合、多角形をAとBに分ける。
2つの切断面があるとき、A側に2つB側に1つ、か、A側に1つB側に2つの可能性があり、どちらでも多角形は3つ。
3つの切断面の時は、A2つ,B2つ。4つの切断面の時は、A2つ,B3つ、か、A3つ,B2つか。

反省

愚直に多角形を分割して多角形を数え上げようとした。
線分Lによって部分的に領域をA,Bの2領域に分けているので、交点に対して、領域A側からくるときの点pA、領域B側からくるときの点pBをそれぞれ交点からちょっとずれた所に作る。
多角形は反時計回りに与えられるので、多角形を分割する場合は、1つ前の交点でA側点qA,B側点qBとすると、qAとpB、qBとpAの辺を追加すれば多角形を分割できる。
すべての辺について、辺をたどって多角形を数え上げれば答えが得られる。