#### World Finals, 2009

Submit Solution(Code Jam Page)

Problem

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.

Input

When you are ready to submit a solution, the file you will download will contain Java source code that produces the input data. You should compile and run that program (see details at the bottom of the problem statement), and it will print the input data for the problem to the standard output stream. The program is guaranteed to run within 30 seconds for the small input, and 90 seconds for the large input if you don't have other resource-intensive processes running.

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 xi, yi. These are the coordinates of the i-th point. There may not be more than one point at the same coordinates.

Output

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.

Limits

1 <= T <= 15
0 <= xi, yi <= 109

Small dataset

3 <= n <= 10000

Large dataset

3 <= n <= 1000000

Sample

 Input ``` public class Input {   public static void main(String[] args) {     // T = 1     System.out.println(1);     // n = 10     System.out.println(10);     // (x[i], y[i]) = (i, i)     for (int i = 0; i < 10; i++)       System.out.println("" + i + " " + i);   } } ``` Output ``` Case #1: 5.656854 ```

Once you're ready to submit a solution, download the program, and run it using the following instructions to get the input file:

Linux instructions:
1. Rename the file to "Input.java" (without quotes).
2. Start a console shell (Applications -> Accessories -> Terminal) and set the current directory to the location of the file ("cd <directory name>").
3. Run
`/usr/lib/jvm/java-6-sun/bin/javac Input.java`
to compile the program.
4. Run
`/usr/lib/jvm/java-6-sun/bin/java -Xmx512M Input >test.txt `
to run the program and save the results to a file named "test.txt". Now that file contains the testcase that you need to solve.

Windows instructions:
1. Rename the file to "Input.java" (without quotes).
2. Start a console shell (Start->Run->cmd.exe and set the current directory to the location of the file ("cd <directory name>").
3. Run
`"C:\Program Files\Java\jdk1.6.0_16\bin\javac" Input.java`
to compile the program.
4. Run
`"C:\Program Files\Java\jdk1.6.0_16\bin\java" -Xmx512M Input >test.txt`
to run the program and save the results to a file named "test.txt". Now that file contains the testcase that you need to solve.

Points Correct Attempted
5pt 17 19
15pt 4 13