题目描述

平面上有 $N$ 个带权点。点 $i$ 位于 $(X_i, Y_i)$，权重为 $W_i$。

本题中，我们需要找出这些点的一个特殊中心。该中心是一个点 $(X, Y)$，使得 $\sum \max(|X - X_i|, |Y - Y_i|) \times W_i$ 最小。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $N$。接下来 $N$ 行，每行包含三个空格分隔的实数 $X_i$、$Y_i$ 和 $W_i$。$X_i$、$Y_i$ 和 $W_i$ 均精确到小数点后两位。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是对于中心 $(X, Y)$ 计算出的 $\sum \max(|X - X_i|, |Y - Y_i|) \times W_i$ 的值。

如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

3
2
0.00 0.00 1.00
1.00 0.00 1.00 
4
1.00 1.00 1.00
1.00 -1.00 1.00
-1.00 1.00 1.00
-1.00 -1.00 1.00 
2
0.00 0.00 1.00
1.00 0.00 2.00

Case #1: 1.0
Case #2: 4.0
Case #3: 1.0

提示

限制条件

$1 \le T \le 10$。

$-1000.00 \le X_i \le 1000.00$。

$-1000.00 \le Y_i \le 1000.00$。

小数据集（测试集 1 – 可见）

$1 \le N \le 100$；

对于所有 $i$，$W_i = 1.0$。

大数据集（测试集 2 – 隐藏）

$1 \le N \le 10000$；

对于所有 $i$，$1.0 \le W_i \le 1000.0$。

翻译由 DeepSeek V4 Pro 完成