题目描述

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 $x_i$, $y_i$. These are the coordinates of the $i$-th point. There may not be more than one point at the same coordinates.

输出格式

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^{-5}$ will be considered correct. Degenerate triangles — triangles with zero area — are ok.

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

Case #1: 5.656854

提示

Limits

• $1 \leq T \leq 15$
• $0 \leq x_i, y_i \leq 10^9$

Small dataset(5 Pts)

• Time limit: 60 15 seconds.
• $3 \leq n \leq 10000$

Large dataset(15 Pts)

• Time limit: 120 30 seconds.
• $3 \leq n \leq 1000000$