A — Shooting a Smart Dart

In a dart game, before a game begins, players randomly shoot many darts onto the dartboard. No two darts share the same position. When the game begins, the game rule is that in each round, a player shoots a new dart, say onto position (x,y). The two old darts (being already on the dartboard) closest to the new dart at (x,y) are used to help determine the score of the round. Let the positions of the two closest old darts be (x₁,y₁) and (x₂,y₂). The score is

that is, the sum of the Euclidean distances between (x,y) and the two closest old darts. To win the game, you need to minimize the score in each round.

Given the positions of the old darts before the game, compute the minimum score a player can get in the first round.

Input Specification

The first line of the input contains an integer N, which is the number of test cases. The first line of each test case contains an integer D (2 ≤ D ≤ 5000), which is the number of old darts on a dartboard. Each of the next D lines gives the position (x,y) of an old dart on the dartboard, where x and y are integers separated by a whitespace, 0 ≤ x, y ≤ 2²⁴. No two darts have the same position on the dartboard.

Output Specification

For each test case, output on a single line the minimum score, truncated to the second decimal place. For example, 3.412 and 3.419 would both truncate to 3.41.

Sample Input

1. 2
2. 5
3. 1 0
4. 2 0
5. 4 0
6. 1 2
7. 3 2
8. 5
9. 1 1
10. 4 1
11. 2 3
12. 5 2
13. 3 6

download as text file

Output for Sample Input

1. 1.00
2. 1.41

download as text file