题目描述

Near the planet Mars, in a faraway galaxy eerily similar to our own, there is a fight to the death between the imperial forces and the rebels. The rebel army has $N$ ships which we will consider as points $(x_i, y_i, z_i)$. Each ship has a receiver with power $p_i$. The rebel army needs to be able to send messages from the central cruiser to all the ships, but they are tight on finances, so they cannot afford a strong transmitter.

If the cruiser is placed at $(x, y, z)$, and one of the other ships is at $(x_i, y_i, z_i)$ and has a receiver of power $p_i$, then the power of the cruiser's transmitter needs to be at least:

$(|x_i - x| + |y_i - y| + |z_i - z|) / p_i$

Your task is to find the position for the cruiser that minimizes the power required for its transmitter, and to output that power.

输入格式

The first line of input gives the number of cases, $T$. $T$ test cases follow.

Each test case contains on the first line the integer $N$, the number of ships in the test case.

$N$ lines follow, each line containing four integer numbers $x_i$, $y_i$, $z_i$ and $p_i$, separated by single spaces. These are the coordinates of the $i$-th ship, and the power of its receiver. There may be more than one ship at the same coordinates.

输出格式

For each input case, you should output:

Case #X: Y

where $X$ is the number of the test case and $Y$ is the minimal power that is enough to reach all the fleet's ships. Answers with a relative or absolute error of at most $10^{-6}$ will be considered correct.

3
4
0 0 0 1
1 2 0 1
3 4 0 1
2 1 0 1
1
1 1 1 1
3
1 0 0 1
2 1 1 4
3 2 3 2

Case #1: 3.50000000
Case #2: 0.00000000
Case #3: 2.33333333

提示

Sample Explanation

In the first test case, the four ships have coordinates $(0, 0, 0), (1, 2, 0), (3, 4, 0), (2, 1, 0)$ and powers $1, 1, 1, 1$ respectively. We can place a cruiser with the power $3.5$ at the coordinates $(1.5, 2, 0)$ which will be able to reach all the ships.

In the second case we can place the cruiser right on top of the ship, with transmitter power 0.

Sample Explanation

• $1 \leq T \leq 10$
• $0 \leq x_i, y_i, z_i \leq 10^6$
• $1 \leq p_i \leq 10^6$

Small dataset (10 Pts, Test set 1 - Visible)

• $1 \leq N \leq 10$

Large dataset (20 Pts, Test set 2 - Hidden)

• $1 \leq N \leq 1000$