prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem G:</font> Malfatti Circles</H1>3 4<p>5The configuration of three circles packed inside a triangle such that each circle is tangent to the6other two circles and to two of the edges of the triangle has been studied by many mathematicians7for more than two centuries. Existence and uniqueness of such circles for an arbitrary triangle8are easy to prove. Many methods of numerical calculation or geometric construction of such9circles from an arbitrarily given triangle have been discovered. Today, such circles are called the10<i>Malfatti circles</i>.11</p>12 13<p>14Figure 7 illustrates an example. The Malfatti circles of the triangle with the vertices (20, 80),15(-40, -20) and (120, -20) are approximately16</p>17 18<ul>19    <li> the circle with the center (24.281677, 45.219486) and the radius 21.565935,</li>20    <li> the circle with the center (3.110950, 4.409005) and the radius 24.409005, and</li>21    <li> the circle with the center (54.556724, 7.107493) and the radius 27.107493.</li>22</ul>23 24<p>25Figure 8 illustrates another example. The Malfatti circles of the triangle with the vertices26(20, -20), (120, -20) and (-40, 80) are approximately27</p>28 29<ul>30    <li> the circle with the center (25.629089, −10.057956) and the radius 9.942044,</li>31    <li> the circle with the center (53.225883, −0.849435) and the radius 19.150565, and</li>32    <li> the circle with the center (19.701191, 19.203466) and the radius 19.913790.</li>33</ul>34<p>35Your mission is to write a program to calculate the radii of the Malfatti circles of the given36triangles.37</p>38 39<center>40<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_malfattiCircles">41</center>42 43 44 45<H2>Input</H2>46 47<p>48The input is a sequence of datasets. A dataset is a line containing six integers <i>x</i><sub>1</sub>, <i>y</i><sub>1</sub> , <i>x</i><sub>2</sub> , <i>y</i><sub>2</sub>, <i>x</i><sub>3</sub>49and <i>y</i><sub>3</sub> in this order, separated by a space. The coordinates of the vertices of the given triangle50are (<i>x</i><sub>1</sub> , <i>y</i><sub>1</sub> ), (<i>x</i><sub>2</sub> , <i>y</i><sub>2</sub> ) and (<i>x</i><sub>3</sub> , <i>y</i><sub>3</sub> ), respectively. You can assume that the vertices form a triangle51counterclockwise. You can also assume that the following two conditions hold.52</p>53 54<ul>55    <li> All of the coordinate values are greater than −1000 and less than 1000.</li>56    <li> None of the Malfatti circles of the triangle has a radius less than 0.1.</li>57</ul>58 59<p>60The end of the input is indicated by a line containing six zeros separated by a space.61</p>62 63<H2>Output</H2>64 65<p>66For each input dataset, three decimal fractions <i>r</i><sub>1</sub> , <i>r</i><sub>2</sub> and <i>r</i><sub>3</sub> should be printed in a line in this67order separated by a space. The radii of the Malfatti circles nearest to the vertices with the68coordinates (<i>x</i><sub>1</sub> , <i>y</i><sub>1</sub> ), (<i>x</i><sub>2</sub> , <i>y</i><sub>2</sub> ) and (<i>x</i><sub>3</sub> , <i>y</i><sub>3</sub> ) should be <i>r</i><sub>1</sub> , <i>r</i><sub>2</sub> and <i>r</i><sub>3</sub> , respectively.69</p>70<p>71None of the output values may have an error greater than 0.0001. No extra character should72appear in the output.73</p>74 75<H2>Sample Input</H2>76<pre>7720 80 -40 -20 120 -207820 -20 120 -20 -40 80790 0 1 0 0 1800 0 999 1 -999 181897 -916 847 -972 890 -92582999 999 -999 -998 -998 -99983-999 -999 999 -999 0 73184-999 -999 999 -464 -464 99985979 -436 -955 -337 157 -439860 0 0 0 0 087</pre>88 89<H2>Output for the Sample Input</H2>90<pre>9121.565935 24.409005 27.107493929.942044 19.150565 19.913790930.148847 0.207107 0.207107940.125125 0.499750 0.499750950.373458 0.383897 0.100456960.706768 0.353509 0.35350997365.638023 365.638023 365.60103898378.524085 378.605339 378.6053399921.895803 22.052921 5.895714100</pre>101 102