Linked Triangles
Time limit2sMemory limit1024 MB
Given six points in 3D space, list every split into two triangles where one triangle is linked to the other by piercing.
- Level
Medium6 of 10
- Topics
- Geometry, Brute force, Implementation
- Solved
- No attempts yet
문제
A triangle △ABC is linked by a triangle △DEF if
- Exactly one edge of △DEF passes through the interior of △ABC (in the plane of △ABC, see figure below) OR
- One vertex of △DEF lies in the interior of △ABC (in the plane of △ABC) and the adjacent edges lie on opposite sides of the plane of △ABC
It turns out that △ABC is linked by △DEF if and only if △DEF is linked by △ABC. In this case we say that △ABC and △DEF are linked.
A set of points in 3-dimensional space is in general position if no four points lie in the same plane (which means no three points lie on the same line).
Given any six points in 3-dimensional space in general position, at least one way exists to split the six points into two sets of three so that the triangles determined by the two subsets are linked. If the points are in general position, case 2 above cannot occur, because it would put four points in the plane of △ABC.
입력
Input consists of six lines. Each line contains three space-separated double precision floating point values x, y and z, giving the coordinates of one point. There are six points in total.
출력
The first line of output contains a single decimal integer N, the number of linked triangles found.
The first line is followed by N lines. Each line contains two space-separated decimal integers m and n, meaning that choosing points 1, m and n as one triangle and the remaining points as the other triangle gives a linked pair. On each of these lines, m < n, and the lines are in lexicographical order. That is, if the line m1 n1 comes before the line m2 n2, then either m1 < m2, or m1 = m2 and n1 < n2.