Armistice Negotiation

Interview

Time limit2sMemory limit512 MB

Summary

Given two sets of points, decide whether a straight line exists that keeps each country's cities strictly on opposite sides.

Level: Medium6 of 10
Topics: Geometry, Divide and conquer, Brute force, Math
Solved: No attempts yet

Problem

Country nein invaded country sys, and sys held the attack off. The two countries now negotiate a new border. The border is a single straight line in the plane: every city held by nein lies on one side of it, and every city held by sys lies on the other side. A city that sits on the line itself is not allowed. Such a line does not always exist, so decide whether one exists.

Input

The first line contains the number of cities of nein, $n$ , and the number of cities of sys, $m$ . ( $1 \le n, m \le 1000$ )

Each of the next $n$ lines contains the coordinates $x$ and $y$ of a city held by nein.

Each of the following $m$ lines contains the coordinates $x$ and $y$ of a city held by sys.

All coordinates are integers with $-10^6 \le x, y \le 10^6$ . No two cities share a position.

Output

Print YES if a line that fully separates the cities of the two countries exists, and NO otherwise.

Examples2

Example 1
Input
```
3 3
1 1
2 2
3 3
1 2
2 3
3 4
```
Expected output
```
YES
```
Example 2
Input
```
3 1
0 0
10 0
0 10
2 2
```
Expected output
```
NO
```