| 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.
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 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