This page is still under construction.

Parts of this page are still being built. What you see may change.

Center

Memory limit1024 MB

Summary
Find a plane point minimizing the weighted sum of Chebyshev distances to N given points, and report that minimum sum.
Level

Medium7 of 10

Topics
Geometry, Math, Binary search, Divide and conquer
Solved
No attempts yet

Problem

There are N weighted points in a plane. Point i is at (Xi, Yi) and has weight Wi.

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-Xi|, |Y-Yi|)*Wi is minimum.

Input

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 Xi, Yi, and Wi. Xi, Yi and Wi have exactly 2 digits after the decimal point.

Output

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-Xi|, |Y-Yi|)*Wi 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.

Constraints

  • 1 ≤ T ≤ 10.
  • -1000.00 ≤ Xi ≤ 1000.00.
  • -1000.00 ≤ Yi ≤ 1000.00.

Examples1

  1. Example 1

    Input
    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
    Expected output
    Case #1: 1.0
Case #2: 4.0
Case #3: 1.0