12612번 - Min Perimeter (Large) 스페셜 저지다국어

You will be given a set of points with integer coordinates. You are asked to compute the smallest perimeter of a triangle with distinct vertexes from this set of points.

The first line of the input data gives you the number of cases, T. T test cases follow. Each test case contains on the first line the integer n, the number of points in the set. n lines follow, each line containing two integer numbers x_i, y_i. These are the coordinates of the i-th point. There may not be more than one point at the same coordinates.

Limits

• 1 <= T <= 15
• 0 <= x_i, y_i <= 10⁹
• 3 <= n <= 1000000

For each test case, output:

Case #X: Y

where X is the number of the test case and Y is the minimum perimeter. Answers with a relative or absolute error of at most 10^-9 will be considered correct. Degenerate triangles — triangles with zero area — are ok.