你还有另一项几何任务。给定两个非退化多边形 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