Cover the Points

zobayer Cybernauts'16 National Pr...
Limits 6s, 512 MB

You are given a set of points P, and a set of target points M in 2D space. For each point M[i] in M, find the minimum angle at M[i] such that all the points P[i] in P are contained within this angle. If the angle is not less than 180 degrees, then you just have to output “TOO WIDE”.

Input

There will be at most 40 test cases. First line contains an integer, T, the number of test cases to process. First line of each test case contains two integers, N and Q, (1 <= N, Q <= 10^5). Then N pairs of integers (x, y), denoting the coordinates of the points in P, followed by Q pairs of integers (x, y), denoting the coordinates of target points in M. All the x and y components of the points are within -10^6 to 10^6. It is guaranteed that there will not be any duplicate points in the same test case.

Output

For each test case, first output the number of test case in the same format as shown below, then output a line for each query point, which is either the minimum angle (in degrees) asked in the problem rounded to 2 decimal points, or the string “TOO WIDE” (without the quotes). Please check sample I/O for more details.

Sample

InputOutput
2
5 3
4 3
0 0
5 0
0 6
2 3
-3 3
3 0
0 -5
2 3
5 3
-1 3
6 4
2 0
10 -3
Case 1:
90.00
TOO WIDE
45.00
Case 2:
36.87
90.00
21.58

Note: Large input file, use faster IO methods. Use acos(-1.0) as the value of PI if needed.

Submit

Login to submit.

Contributors

Statistics

65% Solution Ratio
AashiqEarliest, Aug '18
steinumFastest, 0.5s
steinumLightest, 5.7 MB
steinumShortest, 3440B
Toph uses cookies. By continuing you agree to our Cookie Policy.