Under construction

Still being built. Things may change

Paperweight

Time limit2sMemory limit1024 MB

Summary
For each paperweight, find the faces that stay stable when the center of mass shifts by 0.2 and report the chip's minimum and maximum height over those faces.
Level

Hard8 of 10

Topics
Geometry, Math, Implementation
Solved
No attempts yet

Problem

Your company makes artistic paperweights. Each paperweight is the union of two tetrahedra that share one face. A paperweight is clear solid glass with colored flecks embedded in it. One of the small flecks in each paperweight is actually a tiny RFID chip. This chip must be close to a partnered computer for that computer to operate. Usually the paperweight is placed on top of the computer. The chip has a limited range, however, so its distance from the flat computer top matters. Therefore, it is important to calculate the minimum and maximum possible distance from the chip to the computer top when the paperweight is in a sufficiently stable position. A position is sufficiently stable if the paperweight would not move when the center of mass is shifted by up to 0.2 units in any direction. You may assume the paperweight has uniform density and the chip is small enough to be treated as a point.

Figure 10Figure 11

As an example, consider a paperweight with the vertices of the common face at A = (0, 0, 0), B = (9, 0, 0), C = (0, 8, 0), the fourth vertex of one tetrahedron at D = (0, 0, 9), the fourth vertex of the other tetrahedron at E = (1, 1, -8), and the chip at F = (1, 2, -1). (See Figure 10, where the chip is shown as a red dot.) Placing the paperweight with face BCD on the computer top gives a maximum distance of approximately 3.7 (upper part of Figure 11). Placing it with face ACD on the computer top gives a minimum distance of 1.0 (lower part of Figure 11). Placing it with face ACE on the computer top gives a distance of only 0.9 but is not sufficiently stable.

Input

The input contains one or more test cases. Each test case is a single line that describes the six points A, B, C, D, E, and F, in that order. Each point is described by three integers x, y, and z that give its coordinates. Both tetrahedra have positive volume, D and E lie on opposite sides of the plane defined by A, B, and C, and point F lies strictly inside the paperweight. Each coordinate has absolute value at most 1000. It is always possible to put the paperweight in at least one sufficiently stable position.

The input ends with a line that contains only the integer 0.

Output

For each test case, output the case number followed by the minimum and maximum distances from the chip to the base plane when the paperweight is sufficiently stable. Round these numbers and print them with five digits after the decimal point. Follow the format in the sample output.

Examples1

  1. Example 1

    Input
    0 0 0 9 0 0 0 8 0 0 0 9 1 1 -8 1 2 -1
    0 0 0 7 0 0 0 7 0 0 0 7 -1 -2 -3 2 2 2
    1 2 3 6 2 3 -2 6 3 -1 0 7 4 1 -2 -1 5 3
    0
    
    Expected output
    Case 1: 1.00000 3.73526
    Case 2: 0.57735 2.66967
    Case 3: 0.28214 5.00871