给定一个凸多边形。请数一下包含平面上给定点且它们的顶点是多边形顶点的三角形的数量。可以保证该点不位于多边形的边和对角线上。
输入
第一行包含整数 n — 多边形的顶点数 (3 ≤ n ≤ 100000)。多边形描述如下:n条线,包含按顺时针顺序排列的顶点坐标(整数x和y的绝对值不大于109)。保证给定的多边形是非退化且凸的(没有三个点位于同一条线上)。
下一行包含整数 t (1 ≤ t ≤ 20) — 您应该计算答案的点数。接下来是 t 行,其中包含点的坐标(整数 x 和 y 的绝对值不大于 109)。
输出
输出应包含 t 个整数,每个整数占一行,其中第 i 个数字是第 i 个点的答案。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin (也可以使用 %I64d)。
示例
输入 #1
4 5 0 0 0 0 5 5 5 1 1 3
输出 #1
2
输入 #2
3 0 0 0 5 5 0 2 1 1 10 10
输出 #2
1 0
输入 #3
5 7 6 6 3 4 1 1 2 2 4 4 3 3 2 3 5 5 4 2
输出 #3
5 3 3 4