볼록 껍질의 둘레를 가장 짧게 만들기

평면 위의 점이 세 개 이상 있고 모두 한 직선 위에 있지는 않을 때, 이 점 집합의 볼록 껍질은 집합의 모든 점을 경계나 내부에 포함하는 넓이가 가장 작은 볼록 다각형이다.

점 집합의 좌표가 주어진다. 집합에서 점을 두 개 빼면 볼록 껍질의 둘레가 얼마나 짧아지는지 구하라. 빼는 점은 정확히 두 개이며, 어느 두 점을 뺄지는 직접 고른다.

아래 그림은 예제 세 개에 해당한다. 동그라미로 표시한 점이 제외한 점이고, 굵은 점선이 가장 짧아진 볼록 껍질이다.

예제 1	예제 2	예제 3

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

n
x1 y1
.
.
.
xn yn

$n$은 집합에 속한 점의 개수이고 $5 \le n \le 2000$이다. 각 $i$마다 $(x_i, y_i)$는 $i$번째 점의 좌표이다. $x_i$와 $y_i$는 $-10^6$ 이상 $10^6$ 이하의 정수이다. 집합의 모든 점은 서로 다르다. 즉 $j \ne k$이면 $x_j \ne x_k$ 또는 $y_j \ne y_k$이다. 집합의 점을 $n - 2$개 이상 지나는 직선은 없다.

전체 집합의 볼록 껍질 둘레를 $P$, 점을 두 개 뺀 집합의 볼록 껍질 둘레 중 가장 작은 값을 $Q$라 하자. $P - Q$를 소수점 아래 여섯 자리까지 출력한다.