AOJ 2747 : カーテン - arukukaの日記

素直に実装しても良いが大変そう。
どうしても頂点の数に左右されてしまうので、
どうせだったら座標圧縮をして1x1の正方形について考える。
すると一気に楽になる。

例えばサンプルケース3つ目（問題文に図として紹介されているもの）だと、
以下のようになる。

f:id:arukuka:20170613054722p:plain

窓に内包され、かつカーテンに内包されていないとき、
圧縮した座標を元に戻して足していく。
その合計が答え。

内外判定に外積を使おうとしたが
凹多角形については通用しない。
高専プロコンのときに勉強した
以下のページを参考に実装した。

とは言えど、この内外判定が想定されているような気がしない。
解説を見ると

点と多角形の内包判定は判定したい点から無限に伸びる半直線を考え，
その半直線と多角形の線分が奇数回交差すれば点は多角形に含まれる．

確かに…。

もう少し自分の頭で考えるようにしたい
（せっかくなのでライブラリに追加しましたが）。