#P18850. [Croatian CPC2024] Cetinska Cestogradnja

[Croatian CPC2024] Cetinska Cestogradnja

Cetinska Cestogradnja

题目描述

沙漠中有一条河流,两个城市分别位于它的两端。河流是一条从第一个城市延伸到第二个城市的折线,每一段都严格向北流动,即沿着 yy 坐标增大的方向。

需要修建一条道路连接两座城市。道路可以沿着河岸行进,但每次从河的一侧穿到另一侧,都必须修建一座桥。

在地面上每修建一米道路需要 11 单位费用,每次过河还需要支付固定的建桥费用 TT。城市内的通行问题已经解决,因此道路在起点和终点可以任选河流的一侧。

求完成整个工程所需的最小总费用。

第一个样例的示意图

输入格式

第一行包含整数 NN(2≤N≤15002\le N\le1500)和实数 TT(0<T≤1060<T\le10^6)。NN 是河流折线的节点数,包括两个城市;TT 至多有两位小数。

接下来 NN 行,每行包含两个整数 Xi,YiX_i,Y_i(∣Xi∣,∣Yi∣≤105|X_i|,|Y_i|\le10^5),表示第 ii 个节点的坐标。

保证 Yi<Yi+1Y_i<Y_{i+1},且输入中不存在三个共线的点。道路必须从 (X1,Y1)(X_1,Y_1) 出发,到达 (XN,YN)(X_N,Y_N)。

输出格式

输出一个实数,表示最小总费用。答案与正确结果的绝对误差不超过 10−610^{-6} 即被接受。

样例输入 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

样例解释

第一个样例可参考题目描述中的示意图。