← 返回题目列表

Codeforces · 1599/G

G. 最短路径

中文机器翻译题面 查看原题

给定一个无限平面上的 $$$N$$$ 点,该平面上有笛卡尔坐标系。 $$$N-1$$$ 点位于一条线上,并且有一个点不在该线上。一开始您位于 $$$K$$$ 点,目标是访问每个点。您可以在任意两点之间沿直线移动,并且可以重新访问点。路径的最小长度是多少?

输入

第一行包含两个整数: $$$N$$$ ($$$3 \leq N \leq 2*10^5$$$) - 点数,$$$K$$$ ($$$1 \leq K \leq N$$$) - 起始点的索引。

接下来的 $$$N$$$ 行包含两个整数,$$$A_i$$$, $$$B_i$$$ ($$$-10^6 \leq A_i, B_i \leq 10^6$$$) - 第 $$$i 个$$$ 点的坐标。

输出

输出包含一个数字 - 从点 $$$K$$$ 开始访问所有给定点的最短路径。你的解决方案与主解决方案之间的绝对差异不应超过$$$10^-6$$$;

示例

输入 #1

5 2
0 0
-1 1
2 -2
0 1
-2 2

输出 #1

7.478709

注意

最短路径由以下移动组成:

2 -> 5

5 -> 4

4 -> 1

1 -> 3

没有更短的路径可能。