Overlap

※問題に不備があったので差し替えました。ACされた方はもう一度提出をお願いします。

問題文

頂点数N,Mの多角形A,Bの共通部分の面積を求めよ。入力の座標はccwです。

制約

• $3 \leq N, M \leq 1000$
• $0 \leq |X_{A, i}|, |Y_{A, i}| \leq 10000$
• $0 \leq |X_{B, i}|, |Y_{B, i}| \leq 10000$
• $(X_{A, i}, Y_{A, i}) \neq (X_{A, j}, Y_{A, j})\ (i \neq j)$
• $(X_{B, i}, Y_{B, i}) \neq (X_{B, j}, Y_{B, j})\ (i \neq j)$
• 与えられる多角形は自己交差を持たない
• 与えられる座標はccw(半時計回り、左回り)である
• 入力は全て整数

入力

入力は以下の形式で与えられます。

出力

答えを出力してください。ジャッジ用データとの絶対誤差または相対誤差が$10^{-6}$以下のとき正解とします。ただし、ジャッジ用データと真の値との絶対誤差または相対誤差は$10^{-15}$以下です。

4
0 0
4 0
4 4
0 4
4
2 2
6 2
6 6
2 6

4.00000000000

共通部分は一辺の長さが2の正方形です。

8
0 0
3 0
3 1
1 1
1 2
3 2
3 3
0 3
4
2 -1
4 -1
4 4
2 4

2.00000000000