This page is still under construction.

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

Radar Coverage

Time limit1sMemory limit256 MB

Summary
Find the center of the smallest circle enclosing three given points for each test case.
Level

Medium4 of 10

Topics
Geometry
Solved
No attempts yet

Problem

The army wants to install a new radar that watches three important locations on a map. The X and Y coordinates of the three locations are given. The radar goes where its power can stay as low as possible while all three locations are still watched. Lowering the power shrinks the circular area the radar covers, so the radar sits at the center of the smallest circle that contains all three locations. That circle is unique.

Find the X and Y coordinates of the spot where the radar is installed.

Input

The input holds several test cases. The first line contains the number of test cases NN (1≤N≤1001 \le N \le 100).

Each of the next NN lines contains six integers, the coordinates of the three important locations. Read them two at a time: the X and Y coordinates of the first location, then of the second, then of the third. Every coordinate satisfies 0≤X≤1000 \le X \le 100 and 0≤Y≤1000 \le Y \le 100. The three locations may lie on one straight line, and two or three of them may coincide.

Output

For each test case print one line in the form Case #n: X Y, where nn is the test case number and X and Y are the coordinates of the radar.

Write each coordinate with two decimal places. When a value falls exactly halfway between two numbers with two decimal places, round it up.

Examples2

  1. Example 1

    Input
    3
    2 2 4 4 4 0
    3 2 4 4 4 0
    1 2 4 4 4 0
    
    Expected output
    Case #1: 4.00 2.00
    Case #2: 4.00 2.00
    Case #3: 3.17 2.00
    
  2. Example 2

    Input
    1
    50 50 50 50 50 50
    
    Expected output
    Case #1: 50.00 50.00