分数: 600 点
问题陈述
我们有 N 上的多边形 xy- 平面。
这些多边形的每条边都平行于 x- 或 y- 轴,每个内角是 90 or 270 度。所有这些多边形都很简单。
的 i第一个多边形有 M_i 角落, j- 其中第一个是 (x_{i, j}, y_{i, j}).
该多边形的边是连接 j-th 和 (j+1)第一个角。 (假设 (M_i+1)第一个角是 1-st 角。)
多边形很简单,当......
对于任意两条不相邻的边,它们不相互相交(交叉或接触)。
你被给予 Q 查询。 对于每个 i = 1, 2, \dots, Q, i第查询如下。
- 其中 N 多边形,有多少个有点 (X_i + 0.5, Y_i + 0.5) 在他们里面?
约束
- 1 \leq N \leq 10^5
- 4 \leq M_i \leq 10^5
- 每个 M_i 是偶数。
- \sum_i M_i \leq 4 \times 10^5
- 0 \leq x_{i, j}, y_{i, j} \leq 10^5
- (x_{i, j}, y_{i, j}) \neq (x_{i, k}, y_{i, k}) if j \neq k.
- x_{i, j} = x_{i, j+1} 为 j = 1, 3, \dots M_i-1.
- y_{i, j} = y_{i, j+1} 为 j = 2, 4, \dots M_i。 (假设 y_{i, M_i +1} = y_{i, 1}.)
- 给定的多边形很简单。
- 1 \leq Q \leq 10^5
- 0 \leq X_i, Y_i \lt 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
M_1
x_{1, 1} y_{1, 1} x_{1, 2} y_{1, 2} \dots x_{1, M_1} y_{1, M_1}
M_2
x_{2, 1} y_{2, 1} x_{2, 2} y_{2, 2} \dots x_{2, M_2} y_{2, M_2}
\vdots
M_N
x_{N, 1} y_{N, 1} x_{N, 2} y_{N, 2} \dots x_{N, M_N} y_{N, M_N}
Q
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
输出
打印 Q 行。
的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
3 4 1 2 1 4 3 4 3 2 4 2 5 2 3 5 3 5 5 4 5 6 5 5 3 5 3 6 3 1 4 2 3 4 5
示例输出 1
0 2 1

请注意,不同的多边形可能会相互交叉或接触。
示例输入 2
2 4 12 3 12 5 0 5 0 3 12 1 1 1 9 10 9 10 0 4 0 4 6 6 6 6 2 8 2 8 7 2 7 2 1 4 2 6 4 4 6 3 1 8
示例输出 2
0 2 1 1

虽然多边形很简单,但它们可能不是凸的。