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.
The input consists of several test cases, at most 50.
The first line of each test case contains one integer
$N$ ($3\le N\le 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\le X_ i, Y_ i\le 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.
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
The answer will be accepted as correct if the difference
between $t$ and the exact
answer is at most $0.0005$.
|Sample Input 1
||Sample Output 1