#P17972. Inside Triangle
Inside Triangle
Inside Triangle
题目描述
如果多边形 内部及边界上的每一点都在多边形 的内部或边界上,则称 包含 。如果这些点都严格位于 内部,则称 严格包含 。
给定两个凸多边形 和 ,分别有 个和 个顶点。保证 严格包含 。
从 的顶点中恰好选取三个不同的顶点,组成一个三角形。求这个三角形包含 的选法数。
这里允许 与所选三角形的边界相接触。三个顶点的选择顺序不影响选法。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例中:
第一行一个整数 。接下来 行,每行两个整数 ,按逆时针顺序给出 的顶点坐标。
然后一行一个整数 。接下来 行,每行两个整数 ,按逆时针顺序给出 的顶点坐标。
输出格式
每个测试用例输出一行一个整数,表示合法的选法数。
数据范围
- ;
- ;
- 所有坐标满足 ;
- 两个多边形均为凸多边形,各自的任意三个顶点均不共线,顶点均按逆时针顺序给出;
- 严格位于 内部;
- 所有测试用例的 之和不超过 , 之和也不超过 。
样例
输入
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
样例说明
将第一组中 的六个顶点依次记作 ,符合要求的三角形为 和 。