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”.


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.


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.


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:
Case 2:

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



62% Solution Ratio

AashiqEarliest, Aug '18

steinumFastest, 0.7s

turab_Lightest, 7.3 MB

steinumShortest, 3440B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.