Practice on Toph

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

Rotated Square

By faiyaz26 · Limits 10s, 512 MB

You are given NN 2D points, and some query 2D points. For each query point you need to find the area of maximum bounding empty rotated square where the query point is in the center. Rotated square is a normal axis parallel square but rotated by 45 degrees. And empty rotated square means a rotated square which doesn’t contain any point from the given NN points. Points can be on the border of the square but not inside. Check the diagram to see what a rotated square looks,

If you see the above figure, the left one is normal square, and the right one is rotated square.

Input

Input starts with an integer TT (T5T ≤ 5), denoting the number of test cases. Each case starts with a line containing two integers: pp, qq (1p,q1000001 ≤ p, q ≤ 100000), where pp denotes the number of points and qq denotes the number of query points. Each of the next pp lines contains two integers xx yy denoting the co-ordinate of a point. All the points are distinct. Each of the next qq lines contains two integers xx yy as well. You can assume that the values of the coordinates lie between 00 and 10910^9 (inclusive).

Output

For each case, print the case number in a line first. Then for each query point, you have to print the maximum bounding empty rotated square’s diagonal length centered at the query point. It is guaranteed that the answer will always be integer.

Sample

InputOutput
1
4 2
1 1
100 100
8 9
2 2
0 0
100 100
Case 1:
4
0

For the second query point, you can’t create any rotated square with positive area centered at (100,100) because query point is also one of the given points.


Dataset is huge, use faster I/O.

Discussion

Statistics


20% Solution Ratio

AashiqEarliest, Oct '18

AashiqFastest, 1.5s

AashiqLightest, 16 MB

AashiqShortest, 2865B

Submit

Login to submit

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