#4113. [Wf2015]Qanat

内存限制:128 MiB 时间限制:10 Sec

题目描述

有一座三角形的山,三个顶点分别为(0,0),(w,0),(w,h) (w > h),我们需要挖管道,使得(0,0)->(w,0)这条水平线与(w,h)->(w,0)这条垂直线被挖通,挖的土需要通过所挖的管道运送出来。为了方便这个过程我们可以多挖n个辅助管道,我们需要选择n个x轴上的坐标ai,挖通三角形斜边上对应点到(ai,0)这条垂直线,挖这些管道所产生的土也需要运送出来(运送到山的表面,即斜边上或是(0,0)处),而这些管道也能用来运送土。现在假设管道的宽度可以忽略不记,求最优的坐标选择方案,使得将土运送出来的代价和最小。

输入格式

第一行三个整数w,h(w>h),n。表示山的水平宽与垂直高,以及辅助管道个数。

输出格式

第一行一个实数表示最小代价和。接下来n行按x坐标从小到大输出选择的管道x坐标,n>10则输出前10个即可。
答案保留9位小数。数据保证没有两个管道的x坐标差值小于0.001

样例

样例输入


			
输入1
8 4 1

输入2
195 65 2

样例输出


			
输出
31.500000000
3.000000000

输出2
12220.000000000
48.000000000
108.000000000

数据范围与提示

【数据范围】

1 <= w <= 10000, 1 <= n <= 1000