E. 棱柱体积交 - EOJ Monthly 2019.5 (based on May Selection)

仪表盘所有提交榜单题解

单点时限: 1.0 sec

内存限制: 256 MB

QQ小方最近沉迷于一款在线多人游戏。在这个游戏里，你可以画出一个简单多边形，这个游戏就会通过三维构图，画出以这个简单多边形作为横截面的无限高的棱柱。

但是最近，这个游戏出现了一个 bug ，有一些玩家构造出的棱柱会无缘无故横过来。程序员正在紧急修复这个 bug ，但是很多玩家却觉得这个 bug 能带给游戏更多的乐趣，并开发了一些新玩法。

现在，QQ小方正在和炮哥玩一个游戏：QQ小方和炮哥两个人构造出两个延伸方向互相垂直的棱柱，QQ小方想要和炮哥比，谁更先算出这两个棱柱的体积交。

QQ小方只会处理横截面是凸多边形的情况，但这次不一样。现在给出这两个简单多边形的横截面，你能帮QQ小方计算出一般情况下的体积交吗？

第一行一个整数 $n$ （ $1 \leq n \leq 10^{5}$ ），代表QQ小方给出的多边形顶点数量。

接下来 $n$ 行，第 $i$ 行两个整数 $x_{i}, y_{i}$ （ $- 10^{6} \leq x_{i}, y_{i} \leq 10^{6}$ ），代表QQ小方画出的多边形上第 $i$ 个点的坐标。

接下来一行一个整数 $m$ （ $1 \leq m \leq 10^{5}$ ），代表炮哥给出的多边形的顶点数量。

接下来 $m$ 行，第 $i$ 行两个整数 $p_{i}, q_{i}$ （ $- 10^{6} \leq p_{i}, q_{i} \leq 10^{6}$ ），代表炮哥画出的多边形上第 $i$ 个点的坐标。

多边形的顶点会以顺时针或逆时针的方向给出。

一行一个整数，代表这两个棱柱体的体积交。

如果这个多边形的体积交的精确值是 $\frac{P}{Q}$ ，输出 $P \times Q^{- 1} \mod 10^{9} + 7$ 。

Input

Output

666667713

样例中两柱体的体积交是 $\frac{3125}{3}$ 。

NaN

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2019.5 (based on May Selection)