← 返回题目列表

AtCoder · abc251_g

G. 多边形的交集

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

凸的顶点 N-gon 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 是凸 N-gon,其顶点为 (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."

这里,如果一个点位于多边形的边界上,我们认为该点也包含在多边形中。

约束

  • 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-gon 按逆时针顺序排列。
  • 多边形的每个内角 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 否则。


示例输入 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

多边形 P 是一个五边形 (5-gon) 其顶点是 (-2, -3), (0, -2), (1, 0), (0, 2), (-2, 1).

  • 多边形 P_1 是一个五边形 (5-gon) 通过移位获得 P 的正方向 x- 轴 0 并且在正方向 y- 轴 1,所以它的顶点是 (-2, -2), (0, -1), (1, 1), (0, 3), (-2, 2).
  • 多边形 P_2 是一个五边形 (5-gon) 通过移位获得 P 的正方向 x- 轴 1 并且在正方向 y- 轴 0,所以它的顶点是 (-1, -3), (1, -2), (2, 0), (1, 2), (-1, 1).

因此,以下 应打印 6 行。

  • 的 1-st 行应该是 Yes 因为 (a_1, b_1) = (0, 0) 包含在两者中 P_1 和 P_2.
  • 的 2-nd 行应该是 No 因为 (a_2, b_2) = (1, 0) 包含在 P_2 但不在 P_1.
  • 的 3-rd 行应该是 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.

请注意,多边形边界上的点也被视为包含在多边形中。


示例输入 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