Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Cover the Points

By zobayer · 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.


Discussion
Statistics

35% Solution Ratio

AashiqEarliest, Aug '18

imAnikFastest, 0.9s

turab_Lightest, 7.3 MB

AnachorShortest, 5633B

Submit

Login to submit