Triangle Garden

Time limit1sMemory limit128 MB

Summary
Given a triangle's vertices, compute the two foci and string length of the Steiner inellipse tangent at each side's midpoint.
Level

Hard8 of 10

Topics
Geometry, Math
Solved
No attempts yet

Problem

Sunyoung's landscaping company is known for gardens designed for computer enthusiasts. Its best-known design places a circular pool inside an equilateral triangular terrace so that the pool is tangent to all three sides.

Some customers, however, want a triangular terrace that fits a corner of the garden or an angled boundary instead of an equilateral terrace in the center. For an arbitrary triangular terrace, Sunyoung proposes an elliptical pool tangent to the midpoint of each side of the triangle.

An ellipse can be drawn by fixing two stakes at its foci and using a loop of string. Given the coordinates of the three vertices of the triangle, write a program that outputs the coordinates of the two foci of this ellipse and the required string length. The string length is the sum of the distances from any point on the ellipse to the two foci.

Input

The first line contains an integer N, the number of test cases. (1 ≤ N ≤ 1000)

Each test case is given on one line as six real numbers x1 y1 x2 y2 x3 y3, the coordinates of the three vertices of the triangle.

Output

For each test case, print one line containing fx1 fy1 fx2 fy2 rl, separated by spaces. (fx1, fy1) and (fx2, fy2) are the two foci of the ellipse, and rl is the required string length.

Print the foci so that fx1 <= fx2; if fx1 = fx2, print them so that fy1 <= fy2. Round every value to two digits after the decimal point. If the ellipse is a circle, the two foci are the same point.

Examples1

  1. Example 1

    Input
    3
100 100 200 273.2051 300 100
100 100 100 300 300 100
100 200 100 300 300 100
    Expected output
    200.00 157.71 200.00 157.76 115.47
119.53 213.81 213.81 119.53 163.30
103.94 253.14 229.40 146.86 170.51