Problem C. Min perimeter

Author:Google Code Jam, World Finals 2009   Time limit:10 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  


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 file format

The first line contains one integer N  — number of points.

Each of the next N lines contains two integer numbers xi, yi  — coordinates of i-th point.

Output file format

Output file should contain one real number  — the minimum perimeter. Answers with a relative or absolute error of at most 10 − 7 will be considered correct. Degenerate triangles -— triangles with zero area -— are ok.


0 ≤ n ≤ 106

0 ≤ xi, yi ≤ 109

0.078s 0.017s 13