题目描述

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. 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 \times 100 \times 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.

输入格式

The first line of the input contains two integers $n$ and $s$, where $0 \leq n \leq 10\, 000$ is the number of holes in the cheese, and $1 \le s \le 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 \le x,y,z \le 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.

输出格式

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}$.

题目大意

题目背景

当然，你们都已经听说过国际奶酪加工公司。他们将一块奶酪切成完全相同厚度的薄片的机器是一个经典。最近，他们生产了一种能将球形奶酪（比如荷兰球形干酪）切成薄片的机器——不，不是所有的厚度都一样，而是所有的质量都一样！但是新的挑战摆在面前：切瑞士奶酪。

瑞士奶酪，比如瑞士多孔奶酪，在其中有很多洞，并且这些洞大小可能不同。一片有空洞的奶酪比一片没有洞的奶酪含量更少，质量更轻。所以这是一个挑战：将一块有空洞的奶酪切成质量相同的薄片。

通过智能声呐技术（与过去常常探测未出生的婴儿和油田的技术一样），可以将空洞定位精确到微米级别。对于目前的问题，你可以认为这些洞是完美球体。

每一个未切割的奶酪块尺寸为 $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）世界总决赛

0 4

25.000000000
25.000000000
25.000000000
25.000000000

2 5
10000 10000 20000 20000
40000 40000 50000 60000

14.611103142
16.269801734
24.092457788
27.002992272
18.023645064

提示

Time limit: 3000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2015