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