直角多边形

题目描述

在 $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)$？

输入格式

输入按以下格式从标准输入给出：

$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

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

数据范围

• $1 \le N \le 10^5$
• $4 \le M_i \le 10^5$
• 每个 $M_i$ 都是偶数
• $\sum_i 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 \lt 10^5$
• 输入均为整数