#P18850. [Croatian CPC2024] Cetinska Cestogradnja
[Croatian CPC2024] Cetinska Cestogradnja
Cetinska Cestogradnja
题目描述
沙漠中有一条河流,两个城市分别位于它的两端。河流是一条从第一个城市延伸到第二个城市的折线,每一段都严格向北流动,即沿着 坐标增大的方向。
需要修建一条道路连接两座城市。道路可以沿着河岸行进,但每次从河的一侧穿到另一侧,都必须修建一座桥。
在地面上每修建一米道路需要 单位费用,每次过河还需要支付固定的建桥费用 。城市内的通行问题已经解决,因此道路在起点和终点可以任选河流的一侧。
求完成整个工程所需的最小总费用。

输入格式
第一行包含整数 ()和实数 ()。 是河流折线的节点数,包括两个城市; 至多有两位小数。
接下来 行,每行包含两个整数 (),表示第 个节点的坐标。
保证 ,且输入中不存在三个共线的点。道路必须从 出发,到达 。
输出格式
输出一个实数,表示最小总费用。答案与正确结果的绝对误差不超过 即被接受。
样例输入 1
5 1
0 0
-1 2
4 3
-3 4
1 5
样例输出 1
6.8416192530
样例输入 2
2 1
0 0
0 1
样例输出 2
1.0000000000
样例解释
第一个样例可参考题目描述中的示意图。