分数: 6 点
问题陈述
给定的是凸多边形 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