Minimum Perimeter Triangle

Xaviera faces an interesting problem. Given N points on a plane, she wishes to find the triangle with the minimum perimeter formed by any three points. Note that triangles with three collinear points are also considered valid.

Given the large number of points and their arbitrary distribution, an efficient algorithm is essential for large inputs. However, for the purpose of this problem, you may assume that N is small enough to allow a brute force solution that checks all possible triples.

The perimeter of a triangle formed by points (x₁, y₁), (x₂, y₂), and (x₃, y₃) is given by:

\( P = d((x_1, y_1), (x_2, y_2)) + d((x_2, y_2), (x_3, y_3)) + d((x_3, y_3), (x_1, y_1)) \), where \( d((x_a,y_a),(x_b,y_b)) = \sqrt{(x_a-x_b)^2 + (y_a-y_b)^2} \).

inputFormat

The input begins with an integer N (N ≥ 3), the number of points. Each of the next N lines contains two numbers representing the coordinates of a point.

Example:

3
0 0
0 1
1 0

outputFormat

Output the minimum perimeter among all possible triangles, rounded to 6 decimal places.

sample

3
0 0
0 1
1 0

3.414214