F - 矩形多边形

得分: $600$ 分

问题描述

在 $xy$ 平面上有 $N$ 个多边形。
这些多边形的边都平行于 $x$ 轴或 $y$ 轴，并且每个内角为 $90$ 或 $270$ 度。所有这些多边形都是简单多边形。
第 $i$ 个多边形有 $M_i$ 个拐点，其中第 $j$ 个拐点是 $(x_{i, j}, y_{i, j})$。
多边形的边是连接第 $j$ 个点和第 $(j+1)$ 个点的线段。（假设第 $(M_i+1)$ 个点是第 $1$ 个点。）

你将会得到 $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$
• 如果 $j \neq k$，则 $(x_{i, j}, y_{i, j}) \neq (x_{i, k}, y_{i, k})$。
• 对于 $j = 1, 3, \dots M_i-1$，有 $x_{i, j} = x_{i, j+1}$。
• 对于 $j = 2, 4, \dots M_i$，有 $y_{i, j} = y_{i, j+1}$。（假设 $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$ 个查询的答案。

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

0
2
1

请注意，不同的多边形可能相交或相切。

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

0
2
1
1

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