题目描述

There are $N$ weighted points in a plane. Point $i$ is at ($X_i$, $Y_i$) and has weight $W_i$.

In this problem, we need to find a special center of these points. The center is a point ($X$, $Y$) such that the sum of $\max(|X-X_i|, |Y-Y_i|) \times W_i$ is minimum.

输入格式

The input starts with one line containing exactly one integer $T$, which is the number of test cases. $T$ test cases follow.

Each test case begins with one line containing one integer $N$. $N$ lines follow. Each line contains three space-separated real numbers $X_i$, $Y_i$, and $W_i$. $X_i$, $Y_i$ and $W_i$ have exactly 2 digits after the decimal point.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the sum of $\max(|X-X_i|, |Y-Y_i|) \times W_i$ for center ($X$, $Y$).

$y$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

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

提示

Limits

$1 \le T \le 10$.

$-1000.00 \le X_i \le 1000.00$.

$-1000.00 \le Y_i \le 1000.00$.

Small dataset (Test set 1 - Visible)

$1 \le N \le 100$;

$W_i = 1.0$, for all i.

Large dataset (Test set 2 - Hidden)

$1 \le N \le 10000$;

$1.0 \le W_i \le 1000.0$, for all i.