No.016 D

線分上の点 $P$ を線分の片方の端からもう片方の端まで動かしていくと, 点 $P$ が途中で多角形の辺に出会うと点 $P$ は多角形の内部に入り, さらに多角形の辺に出会うと点 $P$ は多角形の外部に出る. 外部に出たときに多角形からパーツが切り離される.

よって, 点 $P$ が多角形の辺に出会った回数を $n$ とすると, 多角形から $n/2$ 個のパーツが切り離され, 合計で $n/2+1$ 個のパーツに分轄される.

$n$ は多角形の辺のうち線分と交差する辺の個数である.

なお, 線分の交差判定は以下の通りである. (ちょっとぐぐれば出てくる)

点 $A(a_x, a_y), B(b_x, b_y), C(c_x, c_y), D(d_x, d_y)$ があるとき,

$$((c_x-d_x)(a_y-c_y) + (c_y-d_y)(c_x-a_x))((c_x-d_x)(b_y-c_y) + (c_y-d_y)(c_x-b_x)) \lt 0 \\ ((a_x-b_x)(c_y-a_y) + (a_y-b_y)(a_x-c_x))((a_x-b_x)(d_y-a_y) + (a_y-b_y)(a_x-d_x)) \lt 0$$

が成立すれば線分 $AB$ と $CD$ は交差する.

なお, 判定式の途中で int の範囲を超える場合があるので long を使う.