← 返回题目列表

AtCoder · past202112_n

N. 交叉口

中文机器翻译题面 查看原题

分数: 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