427. Hamiltonian polyhedron
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
You are given a convex polyhedron with the sum of its solid angles less than 4 (in steradians; the full angle is in this case equal to 4
pi). Find out whether there exists a cycle that passes through all vertices of the polyhedron exactly once. The cycle must have edges of the polyhedron as its edges, and no edge can be used more than once in the cycle. You can leave some of the edges of the polyhedron unused.
Input
The first line of the input file contains one integer number
f — the number of facets of the polyhedron. Then all
f facets are described. Each description begins with a line with single integer
k — the number of vertices of the facet. The next
k lines contain 3 real numbers each — the vertex coordinates. The points are given in the order they appear on the border of the facet (either clockwise or counter-clockwise). The numbers are given with exactly 9 digits after the decimal point. If a point is listed in several facet descriptions, its coordinates in all descriptions will be exactly the same.
The overall number of vertices of the polyhedron will be at most 100. The overall number of facets and the number of vertices on any facet will be at most 100 as well.
The coordinates of the points are not the exact coordinates in 3-dimensional space, they are rounded to 9 digits after the decimal point from their true value. Some of the points can be very close, but the distance between any two different points is at least 5 · 10
-7. The absolute values of the coordinates of the points do not exceed 1000.
Output
If there is no such cycle as described in the problem statement, output "
No
" on the first line of the output file, otherwise output "
Yes
". In the latter case, output the description of the cycle: on the second line output
n — the number of vertices of the polyhedron; on the next
n lines output the coordinates of the vertices in the order they appear along the cycle, exactly as they were given in the input file, with the same 9 digits after the decimal point.
Example(s)
sample input | sample output |
4
3
100.146488845 0.000000000 0.000000000
100.145878719 0.349576483 0.000000000
-100.145878719 -0.349576483 0.000000000
3
33.382162948 0.000000000 1.219611194
100.146488845 0.000000000 0.000000000
100.145878719 0.349576483 0.000000000
3
33.382162948 0.000000000 1.219611194
100.145878719 0.349576483 0.000000000
-100.145878719 -0.349576483 0.000000000
3
33.382162948 0.000000000 1.219611194
-100.145878719 -0.349576483 0.000000000
100.146488845 0.000000000 0.000000000
|
Yes
4
-100.145878719 -0.349576483 0.000000000
33.382162948 0.000000000 1.219611194
100.146488845 0.000000000 0.000000000
100.145878719 0.349576483 0.000000000
|