Migrated from Lutece 788 Fence Orthogonality

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Evil bunnies are eating Freddy's vegetables. In order to stop them, he decided to build a fence enclosing all vegetables in his garden. Freddy wants the fence to be as cheap (i.e., short) as possible, but for technical reasons, he can only build rectangular fences. For simplicity, we will assume the vegetables are negligibly small and can be represented by points in a two-dimensional plane.

Input

The input consists of several test cases. The first line of each test case contains one integer $N$($3\leq N\leq 10,000$) giving the number of vegetables in the garden. Each of the following $N$ lines contains two integers $X_i$ and $Y_i$ ($0\leq X_i, Y_i\leq 10,000$), giving the coordinates of one vegetable to be protected. No two vegetables have the same coordinates. You may also assume the vegetables are not all on the same straight line.

Output

For each test case, output a single line containing one real number $t$, giving the smallest length of the perimeter of a rectangular fence enclosing all the vegetables. Note that the edges of the rectangle do not need to be parallel with the coordinate axes.The answer will be accepted as correct if the difference between t and the exact answer is at most $0.0005$.

Samples

3
0 0
1 0
0 1
3
10 0
0 10
4 4
4
1 0
0 1
2 1
1 2

4
31.112698
5.656854

Resources

CTU Open Contest, 2013