카나트

카나트는 덥고 건조한 지역에서 물을 끌어오는 관개 시설이다. 2000여 년 전 페르시아에서 처음 만들었고, 모로코에서는 케타라라고 부르며 남부 지역에서는 지금도 쓴다.

카나트의 중심은 지하 수원에서 마을 근처의 출구까지 물을 보내는 거의 수평인 수로다. 여기에 더해 지하 수원에서 산이나 언덕의 지표면까지 수직으로 올라가는 통로가 있고, 이를 어미 우물이라고 부른다. 파낸 흙을 모두 지상으로 옮겨야 하므로 이런 시설을 만드는 비용은 매우 크고, 옛날에는 더 그랬다. 흙은 수로 출구로 나가거나 어미 우물 꼭대기로 올라가야 한다. 그래서 수평 수로 위의 적당한 지점에 수직 통로를 하나 이상 더 뚫는다. 이 통로도 파내야 하지만, 수로에서 나온 흙을 더 짧은 경로로 지상까지 올릴 수 있다.

그림 1: 카나트의 구조.

카나트의 단면을 다음과 같이 모형화한다. 수로 출구는 $(0, 0)$, 수원은 $(w, 0)$, 어미 우물의 꼭대기는 $(w, h)$이고 $w > h$이다. 산의 표면은 $(0, 0)$에서 $(w, h)$까지 이어지는 직선이다.

그림 2: 단순화한 카나트의 단면.

모든 카나트에는 수원에서 산 표면까지 올라가는 어미 우물이 있고, 여기에 수직 통로 $n$개를 더 뚫는다. 수로와 모든 수직 통로는 선분이다. 전체 굴착 비용이 최소가 되도록 수직 통로 $n$개의 위치를 정하라. 굴착 비용은 파낸 흙 전체에 대해 각 흙덩이가 지표면까지 이동하는 거리를 더한 값이고, 흙은 수평 이동과 수직 이동을 자유롭게 섞어서 옮길 수 있다. 예를 들어 지표면에서 시작해 길이가 $\ell$인 경로를 따라(도중에 꺾여도 된다) 이어지는 흙을 파내는 비용은 $\int_0^\ell x\,dx = \frac{1}{2}\ell^2$이다.

첫째 줄에 정수 $w$, $h$, $n$이 공백으로 구분되어 주어진다. ($1 \le w \le 10000$, $1 \le h < w$, $1 \le n \le 1000$)

$w$는 수원에서 수로 출구까지의 수평 거리, $h$는 수원에서 산 표면까지의 수직 거리, $n$은 어미 우물 외에 추가로 뚫는 수직 통로의 개수다.

첫째 줄에 최소 굴착 비용을 출력한다. 이어서 추가로 뚫는 수직 통로 $n$개의 $x$좌표를 증가하는 순서로 한 줄에 하나씩 출력한다. $n$이 10보다 크면 앞의 10개만 출력한다.

모든 값은 소수점 아래 여섯째 자리까지 반올림해 출력한다. 최적 배치는 유일하며, 어떤 통로도 수로 출구나 다른 통로와 0.001 미만으로 가깝게 놓이지 않는다.