Triangle Survey -------- ------ You are the chief programmer for the Triangle Survey Company, and you have a problem. Your company surveys very large properties to accurately locate points on the property, and half the data for a recent job has gone missing. Your survey team did its usual thing: it organized the points into a simple polygon whose vertices are points to be located with all the remaining points to be located inside the polygon, and then triangulated the polygon so that the set of all triangle vertices was exactly the set of points to be located. Then the team measured the lengths of all the triangle edges precise- ly. Lastly the team should have reported: 1) A length list of triples each specifying that the distance from point I to point J is L. 2) A triangle list of triples each specifying that points I, J, K are vertices of a triangle and the order I, J, K is clockwise order. The team reported the length list as usual, but then the team LOST the triangle list. You are being asked to find all the point locations from the length list, without knowing the triangle list a priori. Input ----- A sequence of test cases. Each test case begins with a line containing the test case name. The next line has the form P E where P is the number of points and E is the number of lengths (triangle edges) measured. Points are numbered 1, 2, ..., P. Next come E length list lines each of the form I J L where I and J are numbers of distinct points connected by a triangle edge and L is the length of the edge. Lengths are positive floating point numbers. Points 1 and 2 are at the front of the property, and the first length line has the form: 1 2 L12 You are to assign point 1 the coordinates (0,0) and point 2 the coordinates (L12,0). All other points are to be assigned Y-coordinate > 0, i.e., the property is in a half-plane bounded by its front, and you are to put the property points in the upper half-plane. In addition, to simplify scoring this problem, the X and Y coordinates of all points have been chosen to be integers. 3 <= P <= 10,000 E <= 3*P - 3 1 <= L <= 100,000 The test case name lines are at most 80 characters. Input ends with an end of file. The input will be such that all the point X and Y values are integers such that - 30,000 <= X <= + 30,000 0 <= Y <= + 30,000 where Y == 0 only for points 1 and 2 and X == 0 for point 1 (and maybe other points) Output ------ For each test case, first an exact copy of the test case name line. This is followed by P lines of the form X Y where the I'th such line contains the integer coordi- nates (X,Y) of point I. The first of these lines is therefore `0 0' and the second is `L12 0'. X and Y must be exactly accurate (as integers). Display ------- You can display or print test cases with the commands: display_survey sample.in sample.test print_survey sample.in sample.test where sample.in/sample.test can be replaced by any test case input file and its corresponding output file. Sample Input ------ ----- -- SAMPLE 1 -- 5 8 1 2 100.000000 2 3 100.498756 3 4 22.360680 4 1 142.126704 5 1 64.031242 5 2 64.031242 5 3 84.852814 5 4 80.622577 [See sample.in for more sample input.] Sample Output ------ ------ -- SAMPLE 1 -- 0 0 100 0 110 100 90 110 50 40 [See sample.test for more sample output.] File: trisurvey.txt Author: Bob Walton Date: Sat Oct 19 12:11:06 EDT 2019 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.