AT_abc251_g [ABC251G] Intersection of Polygons

题目描述

在 $xy$ 平面上，给定一个凸 $N$ 边形 $P$，其顶点按逆时针顺序为 $(x_1,\ y_1),\ (x_2,\ y_2),\ \ldots,\ (x_N,\ y_N)$。（其中，$x$ 轴正方向向右，$y$ 轴正方向向上。）

对于该多边形 $P$，考虑 $M$ 个凸 $N$ 边形 $P_1,\ P_2,\ \ldots,\ P_M$。
对于 $i=1,2,\ldots,M$，多边形 $P_i$ 是将多边形 $P$ 沿 $x$ 轴正方向平移 $u_i$，沿 $y$ 轴正方向平移 $v_i$ 得到的多边形。也就是说，$P_i$ 的顶点为 $(x_1+u_i,\ y_1+v_i),\ (x_2+u_i,\ y_2+v_i),\ \ldots,\ (x_N+u_i,\ y_N+v_i)$。

对于 $Q$ 个点 $(a_1,\ b_1),\ (a_2,\ b_2),\ \ldots,\ (a_Q,\ b_Q)$，请判断每个点是否都在$M$ 个多边形 $P_1,\ P_2,\ \ldots,\ P_M$ 的内部或边界上。

注意，如果点在多边形的边界上，也认为该点包含在多边形内。

输入格式

输入按以下格式从标准输入读入。

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$
$M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_Q$ $b_Q$

输出格式

输出 $Q$ 行。对于 $i=1,2,\ldots,Q$，如果点 $(a_i,\ b_i)$ 包含在所有 $M$ 个多边形 $P_1,\ P_2,\ \ldots,\ P_M$ 内（包括边界），则第 $i$ 行输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

5
-2 -3
0 -2
1 0
0 2
-2 1
2
0 1
1 0
6
0 0
1 0
0 1
1 1
-1 -1
-1 -2

输出 #1

Yes
No
Yes
Yes
Yes
No

输入输出样例 #2

输入 #2

10
45 100
-60 98
-95 62
-95 28
-78 -41
-54 -92
-8 -99
87 -94
98 23
87 91
5
-57 -40
-21 -67
25 39
-30 25
39 -20
16
4 5
-34 -8
-63 53
78 84
19 -16
64 9
-13 7
13 53
-20 4
2 -7
3 18
-12 10
-69 -93
2 9
27 64
-92 -100

输出 #2

Yes
Yes
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
No

说明/提示

数据范围

• $3\leq N\leq 50$
• $1\leq M\leq 2\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $-10^8\leq x_i,\ y_i\leq 10^8$
• $-10^8\leq u_i,\ v_i\leq 10^8$
• $-10^8\leq a_i,\ b_i\leq 10^8$
• 所有输入均为整数
• $(x_1,\ y_1),\ (x_2,\ y_2),\ \ldots,\ (x_N,\ y_N)$ 按逆时针顺序构成一个凸多边形
• 多边形 $P$ 的每个内角均小于 $180$ 度

样例解释 1

多边形 $P$ 是以 $(-2,\ -3),\ (0,\ -2),\ (1,\ 0),\ (0,\ 2),\ (-2,\ 1)$ 为顶点的五边形。

• 多边形 $P_1$ 是将 $P$ 沿 $x$ 轴正方向平移 $0$，$y$ 轴正方向平移 $1$ 得到的五边形，顶点为 $(-2,\ -2),\ (0,\ -1),\ (1,\ 1),\ (0,\ 3),\ (-2,\ 2)$。
• 多边形 $P_2$ 是将 $P$ 沿 $x$ 轴正方向平移 $1$，$y$ 轴正方向平移 $0$ 得到的五边形，顶点为 $(-1,\ -3),\ (1,\ -2),\ (2,\ 0),\ (1,\ 2),\ (-1,\ 1)$。

因此，输出如下 $6$ 行：

• $(a_1,\ b_1) = (0, 0)$ 包含在 $P_1$ 和 $P_2$ 内，输出 Yes。
• $(a_2,\ b_2) = (1, 0)$ 只包含在 $P_2$ 内，不包含在 $P_1$ 内，输出 No。
• $(a_3,\ b_3) = (0, 1)$ 包含在 $P_1$ 和 $P_2$ 内，输出 Yes。
• $(a_4,\ b_4) = (1, 1)$ 包含在 $P_1$ 和 $P_2$ 内，输出 Yes。
• $(a_5,\ b_5) = (-1, -1)$ 包含在 $P_1$ 和 $P_2$ 内，输出 Yes。
• $(a_6,\ b_6) = (-1, -2)$ 只包含在 $P_2$ 内，不包含在 $P_1$ 内，输出 No。

注意，位于多边形边界上的点也视为包含在多边形内。

由 ChatGPT 4.1 翻译