odd doctor 已更新

# Solid Geometry Homework

Time Limit
1s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
50.00%(1/2)
Description:

Yellowstar is studying solid geometry recently,and today’s homework is about the space,plane and sphere.So he draw many planes and spheres in the draft paper.These infinite planes and (the surface of)spheres divides the whole drawing space(which can be considered as a infinite 3D-space) into many disjoint regions.Planes and spheres forms the borders of these regions,and they don’t belong to any regions.
Then he comes up with a crazy idea:color the whole space with crayons.He wants that one region has only one color,and two adjacent regions should be colored differently (“adjacent” means the area of two regions’ common borders is greater than zero).Unfortunately,he has only two crayons:a yellow one and a red one.
Yellowstar likes yellow very much,so he gives some coordinates.The regions these points belong to should be colored yellow.
Given positions of all the planes and spheres and the coordinates mentioned above.You should determine:Is there a way to satisfy all the requests?Yellowstar also gives some other coordinates.He wants to know which color they will be while all the requests are satisfied.

Input:

The first line contains an integer T,denoting the number of the test cases.
For each test case, the first line contains 4 integers m,n,p and q, denoting the number of planes,spheres,points and queries.
Then m lines follows,each containing four integers a,b,c and d,denoting the linear equation(ax+by+cz+d=0) of this plane.|a|+|b|+|c|>0.
Then n lines follows,each containing four integers x,y,z and r,denoting the center coordinate(x,y,z) and radius of this sphere.
Then p lines follows, each containing three integers x,y,z,denoting point(x,y,z),the region it belongs to should be colored yellow.
Next q lines are queries.Each contains three integers x,y,z-the coordinate of this point.You need to output which color it will be.

T<=30,0<=m<=100,0<=n<=10,0<=p<=200,1<=q<=2000,|all given numbers|<=10^6，any two planes or spheres aren’t coincidence.No point lies on given planes or spheres.
There is a blank line before each case.

Output:

For each case，if there is no such a coloring way to color the whole space and meet all the requests,print“Impossible”.
Otherwise，for each query，print a line.If the color of this point can be certainly inferred,print it(’Y’ for yellow or ’R’ for red)；if not(both are possible),print”Both”.
Print a blank line between adjacent cases.

Sample Input:
3

1 1 1 2
0 0 1 0
0 0 0 2
0 0 1
0 0 -1
0 0 4

1 1 2 1
0 0 1 0
0 0 0 2
0 0 1
0 0 -1
0 0 4

1 1 0 2
0 0 1 0
0 0 0 2
0 0 4
0 0 -1
Sample Output:
R
R

Impossible

Both
Both
Source:

2015 Multi-University Training Contest 1

Submit