prithivMLmods/Coder-Stat

1 2 3 4<H1>Building a Space Station</H1>5 6<P>7You are a member of the space station engineering team,8and are assigned a task in the construction process of the station.9You are expected to write a computer program to complete the task.10</P>11 12<P>13The space station is made up with a number of units, called <I>cells.</I>14All cells are sphere-shaped, but their sizes are not necessarily uniform.15Each cell is fixed at its predetermined position16shortly after the station is successfully put into its orbit.17It is quite strange that two cells may be touching each other,18or even may be overlapping.19In an extreme case, a cell may be totally enclosing another one.20I do not know how such arrangements are possible.21</P>22 23<P>24All the cells must be connected,25since crew members should be able to walk26from any cell to any other cell.27They can walk from a cell A to another cell B, if,28(1) A and B are touching each other or overlapping,29(2) A and B are connected by a `corridor',30or (3) there is a cell C such that walking from A to C, and also from B to C31are both possible.32Note that the condition (3) should be interpreted transitively.33</P>34 35<P>36You are expected to design a configuration,37namely, which pairs of cells are to be connected with corridors.38There is some freedom in the corridor configuration.39For example, if there are three cells A, B and C,40not touching nor overlapping each other,41at least three plans are possible in order to connect all three cells.42The first is to build corridors A-B and A-C,43the second B-C and B-A, the third C-A and C-B.44The cost of building a corridor is proportional to its length.45Therefore, you should choose a plan with the shortest46total length of the corridors.47</P>48 49<P>50You can ignore the width of a corridor.51A corridor is built between points on two cells' surfaces.52It can be made arbitrarily long, but of course the shortest one is chosen.53Even if two corridors A-B and C-D intersect in space, they are54not considered to form a connection path between (for example) A and C.55In other words, you may consider that two corridors never intersect.56</P>57 58<H2>Input</H2>59 60<P>61The input consists of multiple data sets.62Each data set is given in the following format.63</P>64 65<BLOCKQUOTE>66<I>n</I><BR>67<I>x</I><SUB>1</SUB> <I>y</I><SUB>1</SUB> <I>z</I><SUB>1</SUB> <I>r</I><SUB>1</SUB><BR>68<I>x</I><SUB>2</SUB> <I>y</I><SUB>2</SUB> <I>z</I><SUB>2</SUB> <I>r</I><SUB>2</SUB><BR>69...<BR>70<I>x</I><SUB><I>n</I></SUB> <I>y</I><SUB><I>n</I></SUB> <I>z</I><SUB><I>n</I></SUB> <I>r</I><SUB><I>n</I></SUB><BR>71</BLOCKQUOTE>72 73<P>74The first line of a data set contains an integer <I>n</I>,75which is the number of cells.76<I>n</I> is positive, and does not exceed 100.77</P>78 79<P>80The following <I>n</I> lines are descriptions of cells.81Four values in a line are <I>x-</I>, <I>y-</I> and <I>z-</I>coordinates of82the center, and radius (called <I>r</I> in the rest of the problem) of83the sphere, in this order.84Each value is given by a decimal fraction, with853 digits after the decimal point.86Values are separated by a space character.87</P>88 89<P>90Each of <I>x</I>, <I>y</I>, <I>z</I> and <I>r</I> is positive91and is less than 100.0.92</P>93 94<P>95The end of the input is indicated by a line containing a zero.96</P>97 98<H2>Output</H2>99 100<P>101For each data set, the shortest total length of the corridors102should be printed, each in a separate line.103The printed values should have 3 digits after the decimal point.104They may not have an error greater than 0.001.105</P>106 107<P>108Note that if no corridors are necessary, that is,109if all the cells are connected without corridors,110the shortest total length of the corridors is 0.000.111</P>112 113<H2>Sample Input</H2>114 115<PRE>116311710.000 10.000 50.000 10.00011840.000 10.000 50.000 10.00011940.000 40.000 50.000 10.000120212130.000 30.000 30.000 20.00012240.000 40.000 40.000 20.00012351245.729 15.143 3.996 25.8371256.013 14.372 4.818 10.67112680.115 63.292 84.477 15.12012764.095 80.924 70.029 14.88112839.472 85.116 71.369 5.5531290130</PRE>131 132<H2>Output for the Sample Input</H2>133 134<PRE>13520.0001360.00013773.834138</PRE>139 140 141