CF549E.Sasha Circle

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Berlanders like to eat cones after a hard day. Misha Square and Sasha Circle are local authorities of Berland. Each of them controls its points of cone trade. Misha has nn points, Sasha — mm . Since their subordinates constantly had conflicts with each other, they decided to build a fence in the form of a circle, so that the points of trade of one businessman are strictly inside a circle, and points of the other one are strictly outside. It doesn't matter which of the two gentlemen will have his trade points inside the circle.

Determine whether they can build a fence or not.

输入格式

The first line contains two integers nn and mm (1<=n,m<=10000)(1<=n,m<=10000) , numbers of Misha's and Sasha's trade points respectively.

The next nn lines contains pairs of space-separated integers Mx,MyM_{x},M_{y} ( 104<=Mx,My<=104-10^{4}<=M_{x},M_{y}<=10^{4} ), coordinates of Misha's trade points.

The next mm lines contains pairs of space-separated integers Sx,SyS_{x},S_{y} ( 104<=Sx,Sy<=104-10^{4}<=S_{x},S_{y}<=10^{4} ), coordinates of Sasha's trade points.

It is guaranteed that all n+mn+m points are distinct.

输出格式

The only output line should contain either word "YES" without quotes in case it is possible to build a such fence or word "NO" in the other case.

输入输出样例

  • 输入#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
    

说明/提示

In the first sample there is no possibility to separate points, because any circle that contains both points (1,0),(1,0)(-1,0),(1,0) also contains at least one point from the set (0,1),(0,1)(0,-1),(0,1) , and vice-versa: any circle that contains both points (0,1),(0,1)(0,-1),(0,1) also contains at least one point from the set (1,0),(1,0)(-1,0),(1,0)

In the second sample one of the possible solution is shown below. Misha's points are marked with red colour and Sasha's are marked with blue.

首页