Malfatti Circles

Time limit1sMemory limit128 MB

Summary
Given triangle vertices, compute the radii of the three classical Malfatti circles using the known closed-form formula.
Level

Medium6 of 10

Topics
Math, Geometry, Implementation
Solved
No attempts yet

Problem

Inside a triangle you can draw three circles so that each circle is tangent to the other two circles and to two sides of the triangle. These three circles are called the Malfatti circles. Mathematicians have studied them for more than two centuries, and it has been proven that for any triangle the Malfatti circles always exist and are unique.

For example, if the three vertices of the triangle are (20, 80), (-40, -20), (120, -20), the Malfatti circles are:

  • center (24.281677, 45.219486), radius 21.565935
  • center (3.110950, 4.409005), radius 24.409005
  • center (54.556724, 7.107493), radius 27.107493

And if the vertices are (20, -20), (120, -20), (-40, 80), the Malfatti circles are:

  • center (25.629089, -10.057956), radius 9.942044
  • center (53.225883, -0.849435), radius 19.150565
  • center (19.701191, 19.203466), radius 19.913790

Given a triangle, write a program that computes the radii of its three Malfatti circles.

Input

The input consists of several test cases. Each test case is a single line containing six integers x1,y1,x2,y2,x3,y3x_1, y_1, x_2, y_2, x_3, y_3 separated by spaces. These are the coordinates of the triangle's vertices (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2), (x3,y3)(x_3, y_3), given in counterclockwise order. The input satisfies:

  1. Every coordinate is greater than −1000-1000 and less than 10001000.
  2. No Malfatti circle has a radius smaller than 0.10.1.

The last line contains six zeros and must not be processed.

Output

For each test case, print the radii r1r_1, r2r_2, r3r_3 of the three Malfatti circles on one line, separated by spaces. rir_i is the radius of the circle closest to vertex (xi,yi)(x_i, y_i). Round each radius to exactly six digits after the decimal point (rounding at the seventh decimal place).

Examples1

  1. Example 1

    Input
    20 80 -40 -20 120 -20
    20 -20 120 -20 -40 80
    0 0 1 0 0 1
    0 0 999 1 -999 1
    897 -916 847 -972 890 -925
    999 999 -999 -998 -998 -999
    -999 -999 999 -999 0 731
    -999 -999 999 -464 -464 999
    979 -436 -955 -337 157 -439
    0 0 0 0 0 0
    
    Expected output
    21.565935 24.409005 27.107493
    9.942044 19.150565 19.913790
    0.148847 0.207107 0.207107
    0.125125 0.499750 0.499750
    0.373458 0.383897 0.100456
    0.706768 0.353509 0.353509
    365.638023 365.638023 365.601038
    378.524085 378.605339 378.605339
    21.895803 22.052921 5.895714