Blue x Red = Bang
Time limit1sMemory limit128 MB
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 (), the number of test cases. Each test case begins with a line containing two integers and (), the number of blue and red plugs respectively. The next lines each contain two integers and giving the coordinates of a blue plug, followed by lines each containing two integers and giving the coordinates of a red plug. All coordinates are pairwise distinct and lie in the range to 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.