Optimal Shaft Placement in a Qanat Irrigation System

A qanat is an ancient irrigation system which channels water from an underground water source to an outlet near a civilization. In this problem a simplified cross‐section of the qanat is modeled as follows:

• The channel outlet is at \((0,0)\).
• The underground water source is at \((w,0)\) and the corresponding mountain surface above is at \((w,h)\) (i.e. the top of the mother well), with \(w > h\).
• The mountain surface is a straight line connecting \((0,0)\) and \((w,h)\), so its equation is \(y=\frac{h}{w}x\).

Every qanat has a mandatory (vertical) mother well at \(x=w\) and, in addition, you are allowed to place \(n\) extra vertical shafts along the horizontal underground channel. A shaft is placed at some \(x\)-coordinate \(0 < x < w\) and extends vertically from the channel (\(y=0\)) to the mountain surface (\(y=\frac{h}{w}x\)). The horizontal underground channel extends from \((0,0)\) to \((w,0)\), and it is divided into segments by the positions of the extra shafts (with \(0\) and \(w\) as endpoints).

The excavation cost is measured by the distance that the removed dirt must be transported. In fact, if a continuous section of dirt is excavated and its material must be carried along a path of total length \(\ell\) (possibly including turns), the cost incurred is \[ \int_0^{\ell} x\,dx = \frac{1}{2}\ell^2. \]

For the qanat the cost consists of:

• The cost for each horizontal channel segment: if a segment has length \(d\), its cost is \(\frac{1}{2}d^2\).
• The cost for each vertical shaft: at a position \(x\) (other than the outlet), the shaft has length \(\frac{h}{w} x\) and its cost is \(\frac{1}{2}\Bigl(\frac{h}{w}x\Bigr)^2\). In particular, the mother well at \(x=w\) costs \(\frac{1}{2}h^2\).

Let the extra shafts be placed at \(x_1, x_2, \dots, x_n\) with \(0 < x_1 < x_2 < \cdots < x_n < w\). Then the total cost is \[ C = \frac{1}{2}\Bigl[(x_1-0)^2 + (x_2-x_1)^2 + \cdots + (w-x_n)^2\Bigr] + \frac{1}{2}\Bigl(\frac{h}{w}\Bigr)^2\Bigl(x_1^2+\cdots+x_n^2\Bigr) + \frac{1}{2}h^2. \] You are to choose the positions \(x_1,\dots,x_n\) so that \(C\) is minimized, and then output the minimum total cost.

Input Format

The input begins with an integer \(T\) representing the number of test cases. Each test case consists of a single line containing two real numbers and one integer: \(w\) \(h\) \(n\) (with \(w > h > 0\) and \(n \ge 0\)).

Output Format

For each test case, output a single line containing the minimum excavation cost. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 100\)), the number of test cases. Each of the following \(T\) lines contains two real numbers \(w\) and \(h\) (\(w > h > 0\)) and an integer \(n\) (\(n \ge 0\)).

outputFormat

For each test case, output the minimum total excavation cost on a separate line. The output should have a precision of at least 6 decimal places.

sample

3
10 5 0
10 5 1
12 3 2

62.500000
57.057982
55.469372

</p>