SP3420 FALLINGI - Falling Ice

想象一些冰盘，一个接一个地掉入一个盒子中。每个冰盘会落到它能到达的最低位置，并且不会与之前的冰盘重叠或推开它们。每个冰盘一旦掉落就会固定在原位，不会被后来掉落的冰盘移动。你的任务是计算出所有冰盘最终堆叠的总高度。 为了确保答案的唯一性，假定任何到达盒子底部的冰盘都会尽可能向左滚动。此外，数据经过精心选择，确保每个没有到达底部的冰盘都有一个唯一的最低位置。数据还确保没有“完美契合”的情况出现：每个掉落的冰盘只会与前面的两个圆盘或盒子的侧壁接触。插图中用白色填充的圆盘按它们掉入盒子的顺序标记。第四幅图中的灰色圆盘并不是实际掉落的圆盘，而是为了说明一个问题而存在：灰色圆盘和第 2 号冰盘大小相同，因此第 2 号冰盘本可以放在盒子的最底部，但由于被第 1 号冰盘和盒子的侧壁挡住了，它无法从上面掉下到这个位置。 计算两个相交圆的上交点的方法如下：假设第一个圆的圆心是 $(x_1, y_1)$，半径是 $r_1$；第二个圆的圆心是 $(x_2, y_2)$，半径是 $r_2$。假定第一个圆在第二个圆的左侧，即 $x_1 < x_2$。计算步骤为： $$ \begin{aligned} dx &= x_2 - x_1, \\ dy &= y_2 - y_1, \\ D &= \sqrt{dx^2 + dy^2}, \\ E &= \frac{r_1^2 - r_2^2 + D^2}{2D}, \\ F &= \sqrt{r_1^2 - E^2}; \end{aligned} $$ 上交点的坐标为 $\left(x_1 + \frac{E \cdot dx - F \cdot dy}{D}, y_1 + \frac{F \cdot dx + E \cdot dy}{D}\right)$。

输入包含一个或多个数据集，每行一个数据集。每个数据集由三个或更多用空格分隔的正整数组成，格式为 `w, n, d1, d2, d3, ..., dn`，其中 `w` 是盒子的宽度，`n` 是冰盘的数量，后面的数字表示冰盘的直径，按照它们掉入盒子的顺序排列。假设 `w < 100`，`n < 10`，并且每个直径都小于 `w`。输入以仅包含数字 `0` 的行结束。

对于每个数据集，输出一个行，显示冰盘堆叠的总高度，保留两位小数。 **本翻译由 AI 自动生成**