← 返回题目列表

Codeforces · 166/B

B. 多边形

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

你还有另一项几何任务。给定两个非退化多边形 A 和 B 作为顶点坐标。多边形 A 是严格凸的。多边形B是没有任何自交和自接触的任意多边形。两个多边形的顶点均按顺时针顺序给出。对于每个多边形,没有三个连续的顶点位于同一条直线上。

你的任务是检查多边形B是否严格位于多边形A内部。这意味着多边形B的任何点都应该严格位于多边形A内部。“严格”意味着多边形B的顶点不能位于多边形A的一侧。

输入

第一行包含唯一的整数 n (3 ≤ n ≤ 105) — 多边形 A 的顶点数。然后 n 行包含整数对 xi, yi (|xi|, |yi| ≤ 109) — 多边形 A 第 i 个顶点的坐标。顶点按顺时针顺序给出。

下一行包含一个整数 m (3 ≤ m ≤ 2·104) — 多边形 B 的顶点数。接下来的 m 行包含整数对 xj, yj (|xj|, |yj| ≤ 109) — 多边形 B 第 j 个顶点的坐标。顶点按顺时针顺序给出。

多边形顶点的坐标由单个空格分隔。保证多边形A和B是非退化的,多边形A是严格凸的,多边形B没有自交和自接触,并且对于每个多边形,没有三个连续的顶点位于同一条直线上。

输出

在唯一一行上打印问题的答案 - 如果多边形 B 严格位于多边形 A 内,则打印“YES”,否则打印“NO”(不带引号)。

示例

输入 #1

6
-2 1
0 3
3 3
4 1
3 -2
2 -2
4
0 1
2 2
3 1
1 0

输出 #1

YES

输入 #2

5
1 2
4 2
3 -3
-2 -2
-2 1
4
0 1
1 2
4 1
2 -1

输出 #2

NO

输入 #3

5
-1 2
2 3
4 1
3 -2
0 -3
5
1 0
1 1
3 1
5 -1
2 -1

输出 #3

NO