102115: [AtCoder]ABC211 F - Rectilinear Polygons
Description
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.
Input
题意翻译
## 题目大意 给出平面的 $N$ 个简单多边形,对于每个多边形,其每一条边都平行于 $X$ 轴或 $Y$ 轴,每一个角都为 $90$ 度或 $270$ 度,如图所示。 现在有 $Q$ 次询问,每次给出一个有序整数对 $(X,Y)$ ,求点 $(X+0.5,Y+0.5)$ 被多少个多边形覆盖。 ![](https://img.atcoder.jp/ghi/5fccf008dddd93f10ebfc7f13d04a0e0.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})$ - 输入的所有数据均为整数。 ## 输入格式 第一行输入一个整数 $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)Output
分数:$600$分
问题描述
在$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
虽然多边形是简单的,但它们可能不是凸的。