QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 1024 MB Puntuación total: 100

#4683. 坎儿井

Estadísticas

坎儿井(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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.