1624. 求交集多边形面积

单点时限: 2.0 sec

内存限制: 256 MB

在平面上有两给定的凸多边形,若两凸多边形相交,则它们的交集也是一个凸多边形。若两凸多边形不相交,指的是两凸多边形相离或仅限于边界点与边上相交,则相交面积为 $0$。

你的任务是编程给出交集多边形的面积。

两给定的凸多边形按顺时针方向依次给出多边形每个顶点的坐标。

输入格式

输入文件第一行为一整数 $M$,表示第一个凸多边形的边数,以后 $M$ 行分别给出了 $M$ 个顶点的坐标;接着,给出第二个凸多边形的边数 $N$,以后 $N$ 行分别给出了 $N$ 个顶点的坐标。

$3 \le M,N \le 50$,所有坐标绝对值不超过 $1000$。

输出格式

只一个数据即交集面积,保留两位小数点。

样例

Input
4
0 0
0 1
1 1
1 0
4
-0.5 -0.5
-0.5 0.5
0.5 0.5
0.5 -0.5
Output
0.25

41 人解决,49 人已尝试。

73 份提交通过,共有 151 份提交。

3.6 EMB 奖励。

创建: 16 年,8 月前.

修改: 6 年,6 月前.

最后提交: 9 月,1 周前.

来源: N/A

题目标签