Friend or Foe?
Time limit1sMemory limit128 MB
Given two sets of 3D points, decide whether a single plane separates the Empire points strictly on the positive side from the Alliance points on the non-positive side.
- Level
Medium7 of 10
- Topics
- Geometry, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
Luke has trouble telling apart the star systems of the Rebel Alliance from those of the Empire. He knows the coordinates of every Empire system and every Alliance system, but at warp speed there is no time to look each one up.
His targeting computer is an early model: the only thing it can evaluate is the truth value of the inequality
ax + by + cz + d > 0
where are a system's coordinates and are real coefficients. Fixing one choice of classifies every system at once: a system is treated as belonging to the Empire when the inequality is true, and to the Alliance otherwise.
Such a classifier is usable only when the two groups can be separated by a single plane, i.e. when there exist real numbers for which the inequality holds for every Empire system and for no Alliance system. For each test case, decide whether such coefficients exist.
Input
The input contains several test cases, followed by a line containing -1 -1.
Each test case begins with a line containing the number of Alliance systems. Each following line gives the integer coordinates of one Alliance system. Next comes the number of Empire systems, followed by one line of integer coordinates for each Empire system. The Empire and the Alliance together contain at least one and at most systems, and all systems have distinct coordinates.
Output
For each test case, print a single line containing YES if there exist real coefficients such that for every Empire system and for every Alliance system, or NO if no such coefficients exist.