D. Cutting Cheese
Of course you have all heard of the International Cheese Processing Company. Their machine for cutting a piece of cheese into slices of exactly the same thickness is a classic. Recently they produced a machine able to cut a spherical cheese (such as Edam) i...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
Of course you have all heard of the International Cheese Processing Company. Their machine for cutting a piece of cheese into slices of exactly the same thickness is a classic. Recently they produced a machine able to cut a spherical cheese (such as Edam) into slices – no, not all of the same thickness, but all of the same weight! But new challenges lie ahead: cutting Swiss cheese. Swiss cheese such as Emmentaler has holes in it, and the holes may have different sizes. A slice with holes contains less cheese and has a lower weight than a slice without holes. Picture by Jon Sullivan via Wikimedia Commons So here is the challenge: cut a cheese with holes in it into slices of equal weight. By smart sonar techniques (the same techniques used to scan unborn babies and oil fields), it is possible to locate the holes in the cheese up to micrometer precision. For the present problem you may assume that the holes are perfect spheres. Each uncut block has size 100 × 100 × 100 where each dimension is measured in millimeters. Your task is to cut it into s slices of equal weight. The slices will be 100 mm wide and 100 mm high, and your job is to determine the thickness of each slice.
Input
The first line of the input contains two integers n and s, where 0 ≤ n ≤ 10 000 is the number of holes in the cheese, and 1 ≤ s ≤ 100 is the number of slices to cut. The next n lines each contain four positive integers r, x, y, and z that describe a hole, where r is the radius and x, y, and z are the coordinates of the center, all in micrometers. The cheese block occupies the points (x, y, z) where 0 ≤ x, y, z ≤ 100 000, except for the points that are part of some hole. The cuts are made perpendicular to the z axis. You may assume that holes do not overlap but may touch, and that the holes are fully contained in the cheese but may touch its boundary.
Output
Display the s slice thicknesses in millimeters, starting from the end of the cheese with z = 0. Your output should have an absolute or relative error of at most 10−6 .
Sample Tests
0 425.000000000
25.000000000
25.000000000
25.0000000002 5
10000 10000 20000 20000
40000 40000 50000 6000014.611103142
16.269801734
24.092457788
27.002992272
18.023645064Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
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
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
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.
Code
C++ solution used for this page.
#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;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2015/D-cutting-cheese/solution.texC++ implementationcompetitive_programming/icpc/2015/D-cutting-cheese/solution.cppStatement textcompetitive_programming/icpc/2015/D-cutting-cheese/statement.txtStatement PDFcompetitive_programming/icpc/2015/D-cutting-cheese/statement.pdfMetadatacompetitive_programming/icpc/2015/D-cutting-cheese/meta.jsonYear packetcompetitive_programming/icpc/2015/contest_problems.pdf