prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem A:</font> Lost in Space</H1>3 4<p>5William Robinson was completely puzzled in the music room; he could not find his triangle in6his bag. He was sure that he had prepared it the night before. He remembered its clank when7he had stepped on the school bus early that morning. No, not in his dream. His triangle was8quite unique: no two sides had the same length, which made his favorite peculiar jingle. He9insisted to the music teacher, Mr. Smith, that his triangle had probably been stolen by those10aliens and thrown away into deep space.11</p>12<p>13Your mission is to help Will find his triangle in space. His triangle has been made invisible by the14aliens, but candidate positions of its vertices are somehow known. You have to tell which three15of them make his triangle. Having gone through worm-holes, the triangle may have changed its16size. However, even in that case, all the sides are known to be enlarged or shrunk equally, that17is, the transformed triangle is <i>similar</i> to the original.18 19</p>20 21<H2>Input</H2>22 23<p>24The very first line of the input has an integer which is the number of data sets. Each data set25gives data for one incident such as that of Will’s. At least one and at most ten data sets are26given.27</p>28<p>29The first line of each data set contains three decimals that give lengths of the sides of the original30triangle, measured in centimeters. Three vertices of the original triangle are named P, Q, and31R. Three decimals given in the first line correspond to the lengths of sides QR, RP, and PQ, in32this order. They are separated by one or more space characters.33</p>34<p>35The second line of a data set has an integer which is the number of points in space to be36considered as candidates for vertices. At least three and at most thirty points are considered.37</p>38<p>39The rest of the data set are lines containing coordinates of candidate points, in light years. Each40line has three decimals, corresponding to x, y, and z coordinates, separated by one or more space41characters. Points are numbered in the order of their appearances, starting from one.42</p>43<p>44Among all the triangles formed by three of the given points, only one of them is <i>similar</i> to the45original, that is, ratios of the lengths of any two sides are equal to the corresponding ratios of46the original allowing an error of less than 0.01 percent. Other triangles have some of the ratios47different from the original by at least 0.1 percent.48</p>49<p>50The origin of the coordinate system is not the center of the earth but the center of our galaxy.51Note that negative coordinate values may appear here. As they are all within or close to our galaxy, coordinate values are less than one hundred thousand light years. You don’t have to52take relativistic effects into account, i.e., you may assume that we are in a Euclidean space. You53may also assume in your calculation that one light year is equal to 9.461 &times 10<sup>12</sup> kilometers.54</p>55<p>56A succeeding data set, if any, starts from the line immediately following the last line of the57preceding data set.58 59 60</p>61 62<H2>Output</H2>63 64<p>65For each data set, one line should be output. That line should contain the point numbers of the66three vertices of the similar triangle, separated by a space character. They should be reported67in the order P, Q, and then R.68</p>69 70<H2>Sample Input</H2>71<pre>72273   50.36493  81.61338  79.9659274575  -10293.83 -4800.033 -5296.23876   14936.30  6964.826  7684.81877  -4516.069  25748.41 -27016.0678   18301.59 -11946.25  5380.30979   27115.20  43415.93 -71607.8180   11.51547  13.35555  14.5730781582  -56292.27  2583.892  67754.6283  -567.5082 -756.2763 -118.726884  -1235.987 -213.3318 -216.486285  -317.6108 -54.81976 -55.6303386   22505.44 -40752.88  27482.9487</pre>88 89<H2>Output for the Sample Input</H2>90<pre>911 2 4923 4 293</pre>94 95