← 返回题目列表

AtCoder · abc211_f

F. 直线多边形

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有 N 上的多边形 xy- 平面。
这些多边形的每条边都平行于 x- 或 y- 轴,每个内角是 90 or 270 度。所有这些多边形都很简单。
的 i第一个多边形有 M_i 角落, j- 其中第一个是 (x_{i, j}, y_{i, j}).
该多边形的边是连接 j-th 和 (j+1)第一个角。 (假设 (M_i+1)第一个角是 1-st 角。)

多边形很简单,当......

对于任意两条不相邻的边,它们不相互相交(交叉或接触)。

你被给予 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
  • (x_{i, j}, y_{i, j}) \neq (x_{i, k}, y_{i, k}) if j \neq k.
  • x_{i, j} = x_{i, j+1} 为 j = 1, 3, \dots M_i-1.
  • y_{i, j} = y_{i, j+1} 为 j = 2, 4, \dots M_i。 (假设 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


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