坎儿井(Qanat)是一种广泛用于在炎热干旱气候下输送水源的灌溉系统。这项技术最初由波斯人在 2000 多年前开发。在摩洛哥,坎儿井被称为 khettara,至今仍在该国南部地区使用。
坎儿井的基本特征是一条本质上水平的通道,将水从地下水源输送到靠近文明区域的出口。此外还有一口被称为“母井”的竖井,它从地下水源垂直向上延伸至山脉或丘陵的表面。建造这样的系统极其昂贵,在古代尤其如此,因为从通道和母井中挖掘出的所有材料都必须运送到地面,要么通过通道出口,要么通过母井顶部。为了辅助施工,通常会在地下通道上方的战略位置设置一个或多个额外的竖井。尽管这些竖井也需要挖掘,但它们提供了一种从水平通道提升额外土方的方法,如图 H.1 所示。
图 H.1:坎儿井示意图。
对于本题,将坎儿井的横截面建模如图 H.2 所示,通道出口位于 $(0, 0)$,水源位于 $(w, 0)$,母井顶部位于 $(w, h)$,其中 $w > h$。山体表面沿从 $(w, h)$ 到 $(0, 0)$ 的直线延伸。
图 H.2:坎儿井横截面的简化模型。
每条坎儿井都必须有一口从水源到上方山体表面的垂直母井,以及 $n$ 口额外的垂直竖井。通道和所有竖井均建模为线段。你的目标是确定这些额外竖井的位置,以最小化总挖掘成本。该成本等于每块挖掘出的土方被运送到地表所经过的距离之和(使用水平和垂直移动的任意组合)。例如,挖掘一段从地表开始并沿长度为 $\ell$ 的路径(可能包含转弯)的连续土方,其成本为 $\int_0^\ell x \, dx = \frac{1}{2}\ell^2$。
输入格式
输入包含一行,包含三个整数 $w$ ($1 \le w \le 10\,000$),$h$ ($1 \le h < w$) 和 $n$ ($1 \le n \le 1\,000$)。值 $w$ 是从水源到坎儿井出口的水平距离。值 $h$ 是从水源到山体表面的垂直距离。值 $n$ 是除母井外必须使用的垂直竖井数量。
输出格式
首先,输出最小总挖掘成本。接下来,按递增顺序输出 $n$ 个最优放置的垂直竖井的 $x$ 坐标。如果 $n > 10$,则仅输出前 10 个 $x$ 坐标。误差在 $10^{-4}$ 的绝对或相对误差范围内的答案将被接受。你可以假设存在唯一解。测试用例不会导致竖井距离坎儿井出口或另一口竖井小于 $0.001$ 个单位。
样例
样例输入 1
8 4 1
样例输出 1
31.500000 3.000000
样例输入 2
195 65 2
样例输出 2
12220.000000 48.000000 108.000000
样例输入 3
10000 1 1000
样例输出 3
30141.885677 9.956721 19.913443 29.870164 39.826887 49.783610 59.740334 69.697060 79.653786 89.610515 99.567245