← 返回题目列表

Codeforces · 549/E

E. 萨沙圈

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

伯兰德人喜欢在辛苦一天后吃甜筒。米沙广场和萨沙圆环是贝尔兰的地方当局。他们每个人都控制着自己的锥体贸易点。 Misha 有 n 点,Sasha 有 m 点。由于他们的下属之间经常发生冲突,他们决定以圆圈的形式筑起一道栅栏,使一个商人的贸易点严格在圆圈内,而另一个商人的贸易点严格在圆圈外。两位先生中的哪一位将其交易点放在圆圈内并不重要。

确定他们是否可以建造围栏。

输入

第一行包含两个整数n和m(1≤n,m≤10000),分别是Misha和Sasha的交易点数量。

接下来的 n 行包含一对空格分隔的整数 Mx, My ( - 104 ≤ Mx, My ≤ 104),Misha 交易点的坐标。

接下来的 m 行包含空格分隔的整数对 Sx, Sy (- 104 ≤ Sx, Sy ≤ 104),Sasha 交易点的坐标。

保证所有 n + m 点都是不同的。

输出

唯一的输出行应包含不带引号的单词“YES”(如果可以构建这样的栅栏)或单词“NO”(在其他情况下)。

示例

输入 #1

2 2
-1 0
1 0
0 -1
0 1

输出 #1

NO

输入 #2

4 4
1 0
0 1
-1 0
0 -1
1 1
-1 1
-1 -1
1 -1

输出 #2

YES

注意

在第一个样本中,不可能分离点,因为包含两个点 ( - 1, 0), (1, 0) 的任何圆也包含集合 (0, - 1), (0, 1) 中的至少一个点,反之亦然:包含两个点 (0, - 1), (0, 1) 的任何圆也包含集合 ( - 1, 0), (1, 0)

在第二个示例中,可能的解决方案之一如下所示。米莎的点用红色标记,萨沙的点用蓝色标记。