P16618 [GKS 2017 #B] Center

平面上有 $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}$ 以内，则认为正确。

**限制条件** $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 完成