Making the Perimeter of the Convex Hull Shortest

The convex hull of a set of three or more points in the plane, when the points do not all lie on a single line, is the convex polygon of smallest area that holds every point of the set on its boundary or inside it.

You are given the positions of the points of a set. Find how much shorter the perimeter of the convex hull becomes when two points are excluded from the set. Exactly two points are excluded, and you choose which two.

The figures below correspond to the three sample cases. The circled points are the ones excluded to produce the shortest convex hull, drawn with thick dashed lines.

Sample 1	Sample 2	Sample 3

The input consists of a single test case in the following format.

n
x1 y1
.
.
.
xn yn

Here, $n$ is the number of points in the set, with $5 \le n \le 2000$. For each $i$, $(x_i, y_i)$ gives the coordinates of the $i$-th point of the set. $x_i$ and $y_i$ are integers between $-10^6$ and $10^6$, inclusive. All the points of the set are distinct, that is, $x_j \ne x_k$ or $y_j \ne y_k$ holds when $j \ne k$. No single line passes through $n - 2$ or more points of the set.

Let $P$ be the perimeter of the convex hull of the whole set, and let $Q$ be the smallest perimeter among the convex hulls of the sets obtained by excluding two points. Print $P - Q$ with exactly six digits after the decimal point.