AT_abc211_f [ABC211F] Rectilinear Polygons

题目描述

在坐标轴上有 $N$ 个多边形。

每个多边形的每条边都平行于 $x$ 轴或 $y$ 轴，并且每个内角都是 $90$ 度或 $270$ 度。每个多边形都是简单的。

第 $i$ 个多边形有 $M_i$ 个顶点，第 $j$ 个是 $(x_{i,j},y_{i,j})$。

多边形的边连接第 $j$ 和第 $j+1$ 个顶点（默认第 $M_i+1$ 个顶点是第 $1$ 个）。

:::info[一个多边形是简单的，当……]

对于它的任意两条不相邻的边，它们都不与对方相交（穿过或接触）。

:::

你有 $Q$ 个询问。第 $i$ 个询问形如：

• 在所有 $N$ 个多边形之中，有多少个多边形包含 $(X_i+0.5,Y_i+0.5)$ 这个点？

输入格式

输入数据在标准输入中由下列格式给出：

$$\begin{array}{ll}N\\M_1\\x_{1,1}\quad y_{1,1}\quad x_{1,2}\quad y_{1,2}\quad\dots\quad x_{1,M_1}\quad y_{1,M_1}\\M_2\\x_{2,1}\quad y_{2,1}\quad x_{2,2}\quad y_{2,2}\quad\dots\quad x_{2,M_2}\quad y_{2,M_2}\\\vdots\\M_N\\x_{N,1}\quad y_{N,1}\quad x_{N,2}\quad y_{N,2}\quad\dots\quad x_{N,M_N}\quad y_{N,M_N}\\Q\\X_1\quad Y_1\\X_2\quad Y_2\\\vdots\\X_Q\quad Y_Q\end{array}$$

输出格式

输出 $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

输出

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

输出

0
2
1
1

说明/提示

样例解释

样例 $1$：

注意不同的多边形可能彼此穿过或接触。

样例 $2$：

尽管多边形都是简单的，它们也不一定是凸的。

数据范围

• $1\le N \le 10^5$
• $4\le M_i \le 10^5$
• 每个 $M_i$ 都是偶数。
• $\sum M_i\le 4\times 10^5$
• $0\le x_{i,j},y_{i,j} \le 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\le Q\le 10^5$
• $0\le X_i,Y_i<10^5$
• 所有输入数据都是整数。