삼각형 둘레의 최솟값

좌표가 모두 정수인 점의 집합이 주어진다. 이 집합에서 서로 다른 세 점을 골라 삼각형을 만들 때, 둘레가 가장 짧은 삼각형의 둘레를 구하라.

세 점이 한 직선 위에 놓여 넓이가 0인 삼각형도 삼각형으로 센다. 둘레는 세 점 사이의 유클리드 거리 세 개를 더한 값이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 집합에 속한 점의 개수 $n$이 주어진다. 다음 $n$개의 줄에는 두 정수 $x_i$, $y_i$가 주어지고, 이는 $i$번째 점의 좌표다. 같은 좌표에 두 개 이상의 점이 놓이는 경우는 없다.

제한

• $1 \le T \le 15$
• $0 \le x_i, y_i \le 10^9$
• $3 \le n \le 10^6$

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 둘레의 최솟값이다. $Y$는 소수점 아래 여섯째 자리까지 출력하며, 일곱째 자리에서 반올림한다.