Limits 1s, 256 MB

Night is ending. You have just got NN points in 2D-coordinate plane in your dream. Wait! Things were going well with the points. Suddenly, a circle appeared, which is centered at coordinate (0,0)(0,0) and has a radius of RR. Your mind is telling you to create a convex polygon, whose vertices are subset of those NN points. This convex polygon must enclose the circle completely. That is, no point of the circle (including the points on its boundary) is strictly outside the polygon. The polygon may touch the circle.

This is not enough. You have to find the polygon with smallest area. Output the value of the smallest area×2\times 2. If it is impossible to construct such a polygon, output should be 1-1.

Let’s just solve this problem before the night ends.


First line of the input will have an integer TT (1T100)(1 \le T \le 100), denoting the number of testcases. Each testcase is independent.

First line of each testcase will have an integer NN (1N500)(1 \le N \le 500), denoting the number of points you have got.

Line ii of the next NN lines will have two integers xix_i and yiy_i (104xi,yi104)(-10^4 \le x_i, y_i \le 10^4) denoting the abscissa and ordinate ii-th point respectively, for i=1,2,,Ni=1, 2, \dots, N.

Last line of each testcase will have an integer RR (1R104)(1\le R \le 10^4), denoting the radius of the circle.

Sum of NN over all testcases will not exceed 500500.


Print a separate line for each testcase. Line ii of the output should have the output for ii-th testcase. Output of the ii-th testcase is the value of 2×A2 \times A, where AA is the area of the smallest possible convex polygon. If there is no possible convex polygon, output is 1-1.


-6 0
-4 4
0 6
0 -6
2 2
6 0
5 5

Following figures show the input of 1st testcase and the convex polygon with smallest area. Here the area is 7272.


Login to submit.


75% Solution Ratio
NirjhorEarliest, 4M ago
NirjhorFastest, 0.3s
chrootLightest, 6.0 MB
NirjhorShortest, 1706B
Toph uses cookies. By continuing you agree to our Cookie Policy.