Alan is building a small 3D modeling program that aims to be extremely light-weight yet powerful enough to solve a large number of practical problems. However, he is stuck with the “knife” operation: given a mesh, a plane and a point, the knife operation cuts the mesh with the plane, and removes the part that is in the same half-space as the point. Knowing that programs written in ACM/ICPC competitions are usually very compact, Alan comes for your help. In this problem, you only need to deal with “nice” solid polygonal meshes (3D experts told you that pure triangular meshes are too restrictive for editing), like this: To be precise, “nice” means:
2/4 8. Two adjacent edges on a face can be collinear (but not overlapping). 9. Two adjacent faces (i.e. share a common edge) can be co-planar (but not overlapping). 10. The order of vertices in each face is either clockwise or counter-clockwise. That means the surface normal either point towards or away from the solid. Your task is to compute the volume, surface area of the meshes after cut, as well as the shape of cross-section. Input The input will contain at most 25 test cases. Each test case begins with two integers n, f (4 ≤ n ≤ 1, 000; 4 ≤ f ≤ 1,000), the number of vertices and faces. Each of the following n lines contains three real numbers x, y, z, the coordinates of the vertices. Each of the following f lines describes a face. Each line contains a sequence of integers beginning with v (3 ≤ v ≤ 10), the number of vertices in the face (vertices are numbered 1 to n), followed by a sequence of vertices in the face. The faces are guaranteed to form a single connected solid. The final line of each test case contains 12 real numbers: x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4 that means the solid will be cut with the plane containing triangle P1(x1, y1, z1)−P2(x2, y2, z2)−P3(x3, y3, z3), and you need to remove the half-space containing point P4(x4,y4,z4). It is guaranteed that P1P2P3 is a valid triangle, and P4 is not on the plane of P1P2P3. Coordinates have absolute values not greater than 100. Important: coordinates will be either exact (like integers or finite real numbers like 0.5) or given with enough precision, so you don’t have to worry about precision problems like seemingly non-planar faces. Furthermore, the distance between any mesh vertex and the cut-plane is at least 0.01, so don’t worry about degenerated cases. Output For each test case, print the case number and 5 lines. The first 3 lines are about the solids after cut. Line 1: The number of connected solids after cut. Line 2: The volumes of these solids, in decreasing order. Line 3: The surface areas of these solids, in decreasing order. It is guaranteed that the resulting solids will not touch each other. If nothing is left after cut, line 2 and line 3 should be empty. Next two lines are about the cross-section. Line 4: The number of connected regions in the cross-section. Line 5: The areas of these connected regions, in decreasing order. Note that adjacent co-planar faces in the cross-section should be considered as in the same connected region. Beware that they may contain holes (and the holes can also enclose other connected regions). If the cross-section is empty, line 5 should be empty. All values representing volumes or areas should be rounded to 3 decimal places, and an absolute error of up to 10−3 is allowed. It is guaranteed that all these volumes and areas are greater than 10−2. Explanation: The second case is:
3/4 Note: Be sure that your program can handle complex meshes like this one (one of judge test case): Sample Input 86 000 100 110 010 001 101 111 011 41432 45678 41265 42376 43487 44158 0 0 0.5 1 0 0.5 1 1 0.5 0 0 1 88 000 530 010 -4 3 0 001 531 011
4/4 -4 3 1 3123 3341 3567 3785 41265 42376 43487 44158 -10 2 0 10 2 0 -10 2 1 0 0 0 Sample Output Case 1: 1 0.500 4.000 1 1.000 Case 2: 2 0.417 0.333 6.303 5.236 2 0.833 0.667