N - Intersection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 6 点

問題文

2 次元平面上の凸多角形 S, T が与えられます。

S は N 個の頂点からなり、頂点の座標は反時計回りに (a_1, b_1), \dots, (a_N, b_N) です。
T は M 個の頂点からなり、頂点の座標は反時計回りに (c_1, d_1), \dots, (c_M, d_M) です。

S, T の共通部分の面積を求めてください。

制約

  • 3 \leq N, M \leq 10^3
  • 0 \leq a_i, b_i \leq 3 \times 10^4 \, (1 \leq i \leq N)
  • 0 \leq c_i, d_i \leq 3 \times 10^4 \, (1 \leq i \leq M)
  • (a_1, b_1), \dots, (a_N, b_N) は S の頂点を反時計回りに並べたものである。
  • (c_1, d_1), \dots, (c_M, d_M) は T の頂点を反時計回りに並べたものである。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1 
\vdots
a_N b_N 
c_1 d_1 
\vdots
c_M d_M

出力

答えを出力せよ。 なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。

入力例 1

3 4
3 0
3 4
0 3
1 2
4 2
5 4
4 5

出力例 1

2.00000000000000000000

S, T の共通部分は下図の灰色部分であり、その面積は 2 です。

入力例 2

3 3
0 0
3 0
0 3
3 3
0 3
3 0

出力例 2

0.00000000000000000000

入力例 3

3 3
1 3
0 2
2 0
3 1
2 3
0 1

出力例 3

0.79166666666666662966

Score : 6 points

Problem Statement

Given are convex polygons S and T in a two-dimensional plane.

S has N vertices, with the coordinates (a_1, b_1), \dots, (a_N, b_N) in counter-clockwise order.
T has M vertices, with the coordinates (c_1, d_1), \dots, (c_M, d_M) in counter-clockwise order.

Find the area of the intersection of S and T.

Constraints

  • 3 \leq N, M \leq 10^3
  • 0 \leq a_i, b_i \leq 3 \times 10^4 \, (1 \leq i \leq N)
  • 0 \leq c_i, d_i \leq 3 \times 10^4 \, (1 \leq i \leq M)
  • (a_1, b_1), \dots, (a_N, b_N) are the vertices of S listed in counter-clockwise order.
  • (c_1, d_1), \dots, (c_M, d_M) are the vertices of T listed in counter-clockwise order.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1 
\vdots
a_N b_N 
c_1 d_1 
\vdots
c_M d_M

Output

Print the answer. Your output will be considered correct when the absolute or relative error from our answer is at most 10^{-6}.

Sample Input 1

3 4
3 0
3 4
0 3
1 2
4 2
5 4
4 5

Sample Output 1

2.00000000000000000000

The intersection of S and T, shown gray in the figure below, has an area of 2.

Sample Input 2

3 3
0 0
3 0
0 3
3 3
0 3
3 0

Sample Output 2

0.00000000000000000000

Sample Input 3

3 3
1 3
0 2
2 0
3 1
2 3
0 1

Sample Output 3

0.79166666666666662966