当前没有测试数据。

G - 多边形的交集

得分：$600$ 点

问题描述

在一个二维直角坐标系中，给定一个凸多边形$P$的$N$个顶点$(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)$。（这里，$x$轴的正方向是向右的，$y$轴的正方向是向上的）

基于多边形$P$，我们考虑$M$个凸多边形$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)$。

对于每一个点$(a_1, b_1), (a_2, b_2), \ldots, (a_Q, b_Q)$，判断是否“点同时位于所有的$M$个多边形$P_1, P_2, \ldots, P_M$中”。这里，如果点在多边形的边界上，也视为点在多边形中。

约束条件

• $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$度

输入

从标准输入读入数据，数据格式如下：

$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表示没有。

样例解释

多边形$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$行：

• 第一行输出Yes，因为$(a_1, b_1) = (0, 0)$同时位于$P_1$和$P_2$中。
• 第二行输出No，因为$(a_2, b_2) = (1, 0)$只位于$P_2$中，不在$P_1$中。
• 第三行输出Yes，因为$(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$中。
• 第六行输出No，因为$(a_6, b_6) = (-1, -2)$只位于$P_2$中，不在$P_1$中。

注意：一个处于多边形边界上的点也被视为在多边形内。