F - Rectilinear Polygons 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

xy 平面上に N 個の多角形があります。
これらの多角形は、全ての辺が x 軸または y 軸に平行で、全ての角が 90 度または 270 度で、かつ単純です。
i 個目の多角形は M_i 個の頂点からなり、j 番目の頂点は (x_{i, j}, y_{i, j}) です。
多角形の辺は j 番目の頂点と j+1 番目の頂点を結んでできる線分です(ただし M_i+1 番目の頂点は 1 番目の頂点とします)。

多角形が単純とは

連続しないどの 2 辺も共通部分を持たない(すなわち交差も接触もしない)とき、その多角形を単純といいます。

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


多角形は単純ですが、凸多角形とは限りません。

Score : 600 points

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.)

A polygon is simple when...

for any two of its sides that are not adjacent, they do not intersect (cross or touch) each other.

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.