시간 제한메모리 제한제출정답맞힌 사람정답 비율
90 초 512 MB333100.000%

문제

You will be given a set of points with integer coordinates. You are asked to compute the smallest perimeter of a triangle with distinct vertexes from this set of points.

입력

The first line of the input data gives you the number of cases, T. T test cases follow. Each test case contains on the first line the integer n, the number of points in the set. n lines follow, each line containing two integer numbers xi, yi. These are the coordinates of the i-th point. There may not be more than one point at the same coordinates.

Limits

  • 1 <= T <= 15
  • 0 <= xi, yi <= 109
  • 3 <= n <= 1000000

출력

For each test case, output:

Case #X: Y

where X is the number of the test case and Y is the minimum perimeter. Answers with a relative or absolute error of at most 10-9 will be considered correct. Degenerate triangles — triangles with zero area — are ok.

예제 입력 1

1
10
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9

예제 출력 1

Case #1: 5.656854

채점 및 기타 정보

  • 예제는 채점하지 않는다.