1572 . Perfect Geometree
Description
Geometree is a nightmare. Unlike other nightmares, Geometree is so powerful such that every single object can be very dangerous. Now you have got a tree structure of this Geometree. Please place every object(vertex) onto the plane such that:
(1) The root object is placed at (0, 0)
(2) None of the children have y-coordinate less or equal to parent’s y-coordinate.
(3) The length of each edge must be preserved, that is, the euclidean distance from any parent to its children must equal to the specified edge length. (This “equal” means very close, with error no more than 10-7.)
(4) Objects are dangerous to be put too close, so any two objects must NOT have a distance strictly less than 1 unit length.
Can you solve this problem quickly? perfect! Your nightmare cannot wait.
Warn: 本題有 specialjudge
Input Format
First line contains an integer T (T<=100) indicating the number of test cases. For each test case, first line contains an integer n (1<=n<=100) denoting the number of vertices of the tree. The node is numbered from 0 to n-1, and vertex 0 is root. Each of the next n-1 lines contains three integers a, b, c means that (a, b) is an edge with specified length c. (0<=a, b < n, 1<=c<=100)
It is guaranteed that the input form a correct tree and the answer does exist.
Output Format
For each test case, please output the place of n points, numbered from 0 to n-1 respectively. If there are more than one solutions, output any.
Sample Input 1
1 4 0 1 1 1 2 3 1 3 5
Sample Output 1
0.0 0.0 0.0 1.0 3.0 1.0 0.0 6.0
Hints
Problem Source
Migrated from old NTUJ.
tmt514
Subtasks
| No. | Testdata Range | Score |
|---|