시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 1 1 1 100.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, TT 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 xiyi. 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 <= xiyi <= 109
  • 3 <= n <= 10000

출력

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

힌트