102115: [AtCoder]ABC211 F - Rectilinear Polygons

Problem Statement

We have $N$ polygons on the $xy$-plane.
Every side of these polygons is parallel to the $x$- or $y$-axis, and every interior angle is $90$ or $270$ degrees. All of these polygons are simple.
The $i$-th polygon has $M_i$ corners, the $j$-th of which is $(x_{i, j}, y_{i, j})$.
The sides of this polygon are segments connecting the $j$-th and $(j+1)$-th corners. (Assume that $(M_i+1)$-th corner is the $1$-st corner.)

You are given $Q$ queries. For each $i = 1, 2, \dots, Q$, the $i$-th query is as follows.

• Among the $N$ polygons, how many have the point $(X_i + 0.5, Y_i + 0.5)$ inside them?

Constraints

• $1 \leq N \leq 10^5$
• $4 \leq M_i \leq 10^5$
• Each $M_i$ is even.
• $\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}$ for $j = 1, 3, \dots M_i-1$.
• $y_{i, j} = y_{i, j+1}$ for $j = 2, 4, \dots M_i$. (Assume $y_{i, M_i +1} = y_{i, 1}$.)
• The given polygons are simple.
• $1 \leq Q \leq 10^5$
• $0 \leq X_i, Y_i \lt 10^5$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $Q$ lines.
The $i$-th line should contain the answer to the $i$-th query.

Sample Input 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

Sample Output 1

0
2
1

Note that different polygons may cross or touch each other.

Sample Input 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

Sample Output 2

0
2
1
1

Although the polygons are simple, they may not be convex.

问题描述

在$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$个查询的答案。

样例输入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

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