A Magical Length

All submissions for this problem are available.
Given n points A[1..n] in the 2D plane, where ith point has two attributes A[i].x and A[i].y representing xcoordinate and ycoordinate. Find 3 points A[i], A[j], A[k] (i, j, k are distinct) such that distance(A[i], A[j]) + distance(A[j], A[k]) + distance(A[k], A[i]) is minimized. Here distance(A[i], A[j]) means the Euclid Distance, which is equals to sqrt( (A[i].x  A[j].x)^2 + (A[i].y  A[j].y)^2) You need to output the minimum possible distance.
Input
The first line contains an integer T indicating the number of test cases.
Each test case starts with a positive integer n indicating the number of points.
The following n lines contain two real numbers A[i].x and A[i].y with atmost 6 digits after decimal point describing the coordinates of the point.
Output
Output T lines in total. Each line starts with "Case #: " and followed by minimum length. Here "#" is the number of the test case starting from 1.
Answers within an absolute or relative error of 10^6 will be accepted
Constraints
 1 ≤ T ≤ 10
 3 ≤ n ≤ 100000
 0 ≤ A[i].x, A[i].y ≤ 10000
 A[i].x, A[i].y are real numbers with atmost 6 digits after decimal position.
Example
Input: 1 4 0.0 0.0 2.0 2.0 2.0 0.0 1.0 1.0 Output: Case 1: 4.8284271247
Explanation
One possible solution is to select these 3 points (0, 0), (2, 0), (1, 1), the length is sqrt(2) + sqrt(2) + 2
Author:  admin 
Editorial  http://discuss.codechef.com/problems/ACM14KP1 
Tags  acmkgp14, admin, divideandconq, easymedium 
Date Added:  18092014 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 