ABC016D

https://gyazo.com/ef23ddd076030dd0b8a2ceedbd0ff39d

考えたこと

めんどくさいなこれ

線分と線分の交差判定をして、交点をソート

チョップが外から始まることがわかってるので交互

奇数番目の交点と偶数番目の交点をつなぐ。グラフ的にしか扱わないので切られた辺の両端同士をつなげば良いが、ねじれて繋がないようにする必要がある

内積では判断できないから線分の交差判定をやる

辺集合ができたら連結成分の数を数えればOK

なるほど法線ベクトルに射影して符号が逆であるかをみれば良い

交点を求めるとこまで記事があったのであとでライブラリに入れとこう

公式解説

あれ、切られた辺の数しか数えてない

そうか「多角形」って言ってるから穴はないのか

難しく考えすぎた