This page is still under construction.

Parts of this page are still being built. What you see may change.

Blue x Red = Bang

Time limit1sMemory limit128 MB

Summary
Given up to nine blue and nine red points, decide whether a simple blue polygon and a simple red polygon can be drawn with disjoint interiors and boundaries.
Level

Hard8 of 10

Topics
Geometry, Brute force, Backtracking, Combinatorics
Solved
No attempts yet

Problem

The RB Company is a pioneer in manufacturing electronic boards, and it is now designing a special kind of power board. Each power board is a flat plastic plate carrying colored plugs: blue plugs are null poles and red plugs are phase poles.

The design rule requires connecting all of the blue plugs with straight segments to form a single simple polygon (the blue polygon). Its vertices must be exactly the blue plugs: every blue plug must be a vertex, and no other point may be used. The red plugs must likewise form a simple red polygon. You may assume that no three plugs of the same color are collinear (lie on one line).

For safety, the blue polygon and the red polygon must not intersect; if the two polygons share any point (their intersection is non-empty), a disastrous explosion is inevitable. Some placements of the plugs make it impossible to draw non-intersecting blue and red polygons, and such placements are called disastrous. Write a program that, for each board, decides whether non-intersecting polygons exist.

Input

The first line contains a single integer tt (1≤t≤51 \le t \le 5), the number of test cases. Each test case begins with a line containing two integers bb and rr (3≤b,r<103 \le b, r < 10), the number of blue and red plugs respectively. The next bb lines each contain two integers xx and yy giving the coordinates of a blue plug, followed by rr lines each containing two integers xx and yy giving the coordinates of a red plug. All coordinates are pairwise distinct and lie in the range 00 to 100000100000 inclusive.

Output

For each test case, print a single line containing YES if non-intersecting polygons exist, or NO otherwise. The output is case-sensitive.

Examples1

  1. Example 1

    Input
    2
    4 4
    2 2
    4 2
    2 4
    1 1
    2 5
    2 6
    3 3
    1 3
    3 3
    1 1
    3 1
    2 3
    2 2
    1 4
    3 4
    
    Expected output
    YES
    NO