Intersection of Polygons

题目描述

凸多边形 $N$ 边形 $P$ 在 $xy$ 平面上的顶点按 逆时针 顺序给出为 $(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)$ 的凸 $N$ 边形。 对于每一个点 $(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$，第 $i$ 行应当包含 $Yes$，如果点 $(a_i, b_i)$ 被所有 $M$ 个多边形 $P_1, P_2, \ldots, P_M$ 包含；否则应当包含 $No$。

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

Yes
No
Yes
Yes
Yes
No

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

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)$ 按逆时针顺序构成一个凸 $N$ 边形。 多边形 $P$ 的每个内角均小于 $180$ 度。多边形 $P$ 是一个五边形 ($5$-gon)，其顶点为 $(-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 行应当被输出。

第 1 行应当为 $Yes$，因为 $(a_1, b_1) = (0, 0)$ 同时被 $P_1$ 和 $P_2$ 包含。 第 2 行应当为 $No$，因为 $(a_2, b_2) = (1, 0)$ 被 $P_2$ 包含但不被 $P_1$ 包含。 第 3 行应当为 $Yes$，因为 $(a_3, b_3) = (0, 1)$ 同时被 $P_1$ 和 $P_2$ 包含。 第 4 行应当为 $Yes$，因为 $(a_4, b_4) = (1, 1)$ 同时被 $P_1$ 和 $P_2$ 包含。 第 5 行应当为 $Yes$，因为 $(a_5, b_5) = (-1, -1)$ 同时被 $P_1$ 和 $P_2$ 包含。 第 6 行应当为 $No$，因为 $(a_6, b_6) = (-1, -2)$ 被 $P_2$ 包含但不被 $P_1$ 包含。

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

标签: AtCoder|abc251G

来源

AtCoder|abc251G