CodeChef July Challenge: Defend the Recipe

解法

各線分による領域の共通部分を取ればよい。これは直線を使って凸包を作る問題となる。

次の図はサンプル 2の領域。

もう少し複雑な図形なら次のような感じ。

直線から凸包を作るには、点から凸包を作るのと大体同じ手法が使える。直線を方向ベクトルで偏角ソートし、逐次直線を追加していけばいい。

直線から凸包を作るのは convex hull trick で慣れてたけど、今回みたいに全方位の直線はやったことがなくてかなりバグらせてた。