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.
*