AtCoder Beginner Contest(ABC) #016 D - 一刀両断

[問題]

多角形(凹凸)と線分1本が与えられる。線分により、多角形は何個に分割されるか？

[解答]

多角形の各辺について、線分との交差判定を行う。交差判定はベクトルの外積の符号判定を用いて行う(AB x AC * AB x AD < 0 && CD x CA * CD * CB <0)。交差の数の半分が分割数なので+1して返す。

[コード](Ruby)

[感想]

線分の本数が増えると難しそう。。。