P6907 [ICPC 2015 WF] Cutting Cheese

# 题目背景 当然，你们都已经听说过国际奶酪加工公司。他们将一块奶酪切成完全相同厚度的薄片的机器是一个经典。最近，他们生产了一种能将球形奶酪（比如荷兰球形干酪）切成薄片的机器——不，不是所有的厚度都一样，而是所有的质量都一样！但是新的挑战摆在面前：切瑞士奶酪。 瑞士奶酪，比如瑞士多孔奶酪，在其中有很多洞，并且这些洞大小可能不同。一片有空洞的奶酪比一片没有洞的奶酪含量更少，质量更轻。所以这是一个挑战：将一块有空洞的奶酪切成质量相同的薄片。 通过智能声呐技术（与过去常常探测未出生的婴儿和油田的技术一样），可以将空洞定位精确到微米级别。对于目前的问题，你可以认为这些洞是完美球体。 每一个未切割的奶酪块尺寸为 $100\times100\times100$，其中单位为毫米。你的任务是把它切成 $s$ 个质量相等的薄片。这些薄片宽度和高度都应当是 $100\operatorname{mm}$，然后你的工作是求出每个薄片的厚度。 ## 简化题意 有一个 $100 \text{mm} \times 100 \text{mm} \times 100 \text{mm}$ 的质地均匀的正方体，垂直于 $z$ 轴的切成 $s$ 个薄片，使得每一片质量相等。每一薄片宽度和高度都是 $100 \text{mm}$，请从奶酪底端 $z=0$ 开始依次输出每一片的厚度。

输入的第一行包含两个整数 $n$ 和 $s$，其中 $0 \leq n \leq 10000$ 表示奶酪中洞的个数，然后 $1 \le s \le 100$ 表示要切割的薄片数。接下来的 $n$ 行分别包含四个描述空洞的正整数 $r,x,y,z$，其中 $r$ 表示半径，$x$、$y$ 和 $z$ 表示空洞中心坐标，都以微米为单位。 奶酪的圆心 $(x,y,z)$ 中 $0 \le x,y,z \le 100000$，除了某个孔的部分点（即某个孔的部分点可能超出该范围，但是圆心一定在这之内）。刀切的方向垂直于 $z$ 轴。 你可以认为这些洞没有重叠但是可能接触，并且这些孔完全包含在奶酪里，但可能接触奶酪的边界。

输出保留 $9$ 位小数。从奶酪底端 $z=0$ 开始，以毫米为单位输出 $s$ 个薄片厚度。相对误差或绝对误差不能超过 $10^{-6}$。

时间限制：$3000 \text{ms}$，空间限制：$1048576\text{kB}$。 2015年国际大学生编程大赛（ACM-ICPC）世界总决赛