\(S\) と \(T\) の共通部分は凸多角形になり、その頂点は

• \(S\) の辺と \(T\) の辺の交点
• \(S\) の頂点であり、\(T\) の内部に含まれるもの
• \(T\) の頂点であり、\(S\) の内部に含まれるもの

のいずれかであるため、\(O(NM)\) で列挙できます。また、これらの頂点は高々 \(O(N+M)\) 個なので、\(O((N+M)\log(N+M))\) で面積を求めることができます。

サンプル1のように、一方の頂点が他方の辺上にある場合や、サンプル2のように、\(S\) の辺と \(T\) の辺の一部が重なっている場合などに注意してください。