Time Limit: 2 sec / Memory Limit: 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.