[Wf2015]Qanat

时间限制:10s      空间限制:128MB

题目描述

有一座三角形的山,三个顶点分别为(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


题目来源

鸣谢GyWXwshMy提供译文及数据