#P17972. Inside Triangle

Inside Triangle

Inside Triangle

题目描述

如果多边形 P2P_2 内部及边界上的每一点都在多边形 P1P_1 的内部或边界上,则称 P1P_1 包含 P2P_2。如果这些点都严格位于 P1P_1 内部,则称 P1P_1 严格包含 P2P_2。

给定两个凸多边形 PP 和 QQ,分别有 nn 个和 mm 个顶点。保证 PP 严格包含 QQ。

从 PP 的顶点中恰好选取三个不同的顶点,组成一个三角形。求这个三角形包含 QQ 的选法数。

这里允许 QQ 与所选三角形的边界相接触。三个顶点的选择顺序不影响选法。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例中:

第一行一个整数 nn。接下来 nn 行,每行两个整数 x,yx,y,按逆时针顺序给出 PP 的顶点坐标。

然后一行一个整数 mm。接下来 mm 行,每行两个整数 x,yx,y,按逆时针顺序给出 QQ 的顶点坐标。

输出格式

每个测试用例输出一行一个整数,表示合法的选法数。

数据范围

  • 1≤T≤10001\le T\le1000;
  • 3≤n,m≤3×1053\le n,m\le3\times10^5;
  • 所有坐标满足 ∣x∣,∣y∣≤109|x|,|y|\le10^9;
  • 两个多边形均为凸多边形,各自的任意三个顶点均不共线,顶点均按逆时针顺序给出;
  • QQ 严格位于 PP 内部;
  • 所有测试用例的 nn 之和不超过 5×1055\times10^5,mm 之和也不超过 5×1055\times10^5。

样例

输入

3
6
-5 0
-4 -4
0 -4
3 1
2 5
-3 4
4
-2 1
-2 0
0 0
0 1
6
-5 0
-4 -4
0 -4
3 1
2 5
-3 4
4
-1 1
-1 0
0 0
0 1
7
1 -3
4 -1
5 0
1 4
0 4
-1 0
0 -2
3
0 0
2 0
0 2

输出

2
4
6

样例说明

将第一组中 PP 的六个顶点依次记作 A,B,C,D,E,FA,B,C,D,E,F,符合要求的三角形为 ACEACE 和 BDFBDF。