AT_abc211_f [ABC211F] Rectilinear Polygons

题目描述

## 题目大意 给出平面的 $N$ 个简单多边形,对于每个多边形,其每一条边都平行于 $X$ 轴或 $Y$ 轴,每一个角都为 $90$ 度或 $270$ 度,如图所示。 现在有 $Q$ 次询问,每次给出一个有序整数对 $(X,Y)$ ,求点 $(X+0.5,Y+0.5)$ 被多少个多边形覆盖。 ![](https://img.atcoder.jp/ghi/5fccf008dddd93f10ebfc7f13d04a0e0.png)

输入格式

第一行输入一个整数 $N$ 。 后面 $1$ 至 $N+1$ 行,第 $i$ 行先输入一个整数 $M_i$ ,再输入 $2\times M_i$ 个整数:$x_{i,1},y_{i,1},x_{i,2},y_{i,2},...,x_{i,M_i},y_{i,M_i}$ 。其相邻两点所连成的线段即为多边形的边。 接下来读入一个数 $Q$ 。表示询问 $Q$ 次。 后面 $Q$ 行每行有两个数 $X_i,Y_i$ ,表示询问点 $(X_i+0.5,Y_i+0.5)$ 被多少个多边形覆盖。

输出格式

共 $Q$ 行,每一行有一个整数表示答案。 ### 样例解释 1.如上图 2.如下图 ![](https://img.atcoder.jp/ghi/1c97f791a2aadcf5637b1f10736fb820.png)

说明/提示

- $1\le N \le 10^5$ - $4\le M_i \le 10^5$ - $\forall M_i,i\isin [1,N],M_i$ 为偶数 - $\sum M_i\le 4\times 10^5$ - $0\le x_{i,j},X_i,y_{i,j},Y_i \le 10^5$ - $1\le Q \le 10^5$ - 对于 $j=1,3,5... M_i-1$ ,都有 $x_{i,j}=x_{i,j+1}$ - 对于 $j=2,4,6... M_i$ ,都有 $y_{i,j}=y_{i,j+1}$ (特殊的, $y_{i,M_i}=y_{1,1}$ ) - 对于任意一个给出多边形,没有重合的顶点。即若 $k \not= j$ ,则 $(x_{i,j},y_{i,j}) \not= (x_{i,k},y_{i,k})$ - 输入的所有数据均为整数。