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。

数据范围

• $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 翻译