EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2010
ICPC 2010

K. Paperweight

Problem ID: weight Your company makes artistic paperweights. Each paperweight is the union of two tetrahedra that share one face. They are clear solid glass with embedded colored flecks. One of the little flecks in each paperweight is actually a tiny RFID c...

Updated May 21, 2026
Track ICPC
Year 2010
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

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

z                                                                        E
B                          y
      Figure 10                                                    Figure 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 results in the maximum distance of approximately 3.7 (upper part of Figure 11). Placing the paperweight with face ACD on the computer results in the minimum distance of 1.0 (lower part of Figure 11). Placing the paperweight with face ACE on the computer results in 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 describing the six points A, B, C, D, E, and F, in that order. Each point is in turn described by three integers x, y and z giving its coordinates. Both of the two tetrahedra have positive volume, D and E lie on opposite sides of the plane defined by the points A, B, C, and point F lies strictly inside the paperweight. Each coordinate is bounded by 1000 in absolute value. It is always possible to put the paperweight in at least one sufficiently stable position.

The input is terminated by a line containing only the integer 0.

Output

For each test case, display the case number followed by the minimum and maximum distances from the chip to the base plane when the paperweight is sufficiently stable. These numbers should be rounded and displayed to five digits after the decimal point. Follow the format in the sample output.

Sample Tests

Sample
Sample 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
Sample Output 
Case 1: 1.00000 3.73526
Case 2: 0.57735 2.66967
Case 3: 0.28214 5.00871
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2010/K-paperweight/solution.texC++ implementationcompetitive_programming/icpc/2010/K-paperweight/solution.cppStatement textcompetitive_programming/icpc/2010/K-paperweight/statement.txtStatement PDFcompetitive_programming/icpc/2010/K-paperweight/statement.pdfMetadatacompetitive_programming/icpc/2010/K-paperweight/meta.jsonYear packetcompetitive_programming/icpc/2010/contest_problems.pdf