Processing math: 100%

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  

Statement

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 107 will be considered correct. Degenerate triangles -— triangles with zero area -— are ok.

Constraints

0n106

0xi,yi109


0.044s 0.007s 13