Point Separation

Time limit1sMemory limit128 MB

Summary
Decide if two colored point sets on a plane can be separated by a straight line, essentially checking convex hull separation.
Level

Medium6 of 10

Topics
Geometry, Math
Solved
No attempts yet

Problem

There are several black points and white points on a plane. You want to draw an infinitely long straight line to separate the white points from the black points. The line must not pass through any point. Of the two groups divided by the line, one group must contain only white points and the other only black points.

In the figure below, the leftmost example can have its two kinds of points divided by the dashed line, but the remaining examples cannot be separated by any line.

Given the coordinates of the white and black points, write a program that determines whether the points can be separated by a straight line.

Input

The first line contains the number of test cases TT. The first line of each test case contains the number of black points nn and the number of white points mm, separated by a space. Both nn and mm are at most 100100. The following nn lines contain the coordinates of the black points, separated by spaces, and the next mm lines contain the coordinates of the white points.

The xx and yy coordinates of every point are integers between 00 and 1000010000, inclusive. Also, no two points are at the same position.

Output

For each test case, print YES if the points can be separated by a line as described, and NO otherwise.

Examples1

  1. Example 1

    Input
    10
3 3
100 700
200 200
600 600
500 100
500 300
800 500
3 3
100 300
400 600
400 100
600 400
500 900
300 300
3 4
300 300
500 300
400 600
100 100
200 900
500 900
800 100
1 2
300 300
100 100
500 500
1 1
100 100
200 100
2 2
0 0
500 700
1000 1400
1500 2100
2 2
0 0
1000 1000
1000 0
0 1000
3 3
0 100
4999 102
10000 103
5001 102
10000 102
0 101
3 3
100 100
200 100
100 200
0 0
400 0
0 400
3 3
2813 1640
2583 2892
2967 1916
541 3562
9298 3686
7443 7921
    Expected output
    YES
NO
NO
NO
YES
YES
NO
NO
NO
YES