Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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