23993번 - Center 서브태스크스페셜 저지다국어

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|)*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|)*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.

• 1 ≤ T ≤ 10.
• -1000.00 ≤ X_i ≤ 1000.00.
• -1000.00 ≤ Y_i ≤ 1000.00.

시간 제한: 20 초

• 1 ≤ N ≤ 100;
• W_i = 1.0, for all i.

시간 제한: 40 초

• 1 ≤ N ≤ 10000;
• 1.0 ≤ W_i ≤ 1000.0, for all i.