308924: CF1599G. Shortest path

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Shortest path

题意翻译

### 题目描述 在一个平面内有 $N$ 个点,其中的 $N-1$ 个点在一条直线上,另一个点不在这条直线上,现在需要从点 $K$ 出发,遍历所有的点 。每次可以选择任意两点间的直线移动,可以重复经过这些点,求最小的移动路径 。 ### 输入格式 第一行包含两个整数,一个整数 $N$ $(3\leq N\leq 2\times 10^5)$ 表示点的数量 ,一个整数 $K$ $(1\leq K\leq N)$ 表示起点的编号 。 接下来 $N$ 行,每行两个整数 $A_i$ , $B_i$ $(-10^6\leq A_i,B_i\leq10^6)$ 表示第 $i$ 个点的坐标 。 ### 输出格式 一个整数,表示最小移动路径的长度,误差不超过 $10^{-6}$ 。

题目描述

You are given $ N $ points on an infinite plane with the Cartesian coordinate system on it. $ N-1 $ points lay on one line, and one point isn't on that line. You are on point $ K $ at the start, and the goal is to visit every point. You can move between any two points in a straight line, and you can revisit points. What is the minimum length of the path?

输入输出格式

输入格式


The first line contains two integers: $ N $ ( $ 3 \leq N \leq 2*10^5 $ ) - the number of points, and $ K $ ( $ 1 \leq K \leq N $ ) - the index of the starting point. Each of the next $ N $ lines contain two integers, $ A_i $ , $ B_i $ ( $ -10^6 \leq A_i, B_i \leq 10^6 $ ) - coordinates of the $ i-th $ point.

输出格式


The output contains one number - the shortest path to visit all given points starting from point $ K $ . The absolute difference between your solution and the main solution shouldn't exceed $ 10^-6 $ ;

输入输出样例

输入样例 #1

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

输出样例 #1

7.478709

说明

The shortest path consists of these moves: 2 -> 5 5 -> 4 4 -> 1 1 -> 3 There isn't any shorter path possible.

Input

题意翻译

### 题目描述 在一个平面内有 $N$ 个点,其中的 $N-1$ 个点在一条直线上,另一个点不在这条直线上,现在需要从点 $K$ 出发,遍历所有的点 。每次可以选择任意两点间的直线移动,可以重复经过这些点,求最小的移动路径 。 ### 输入格式 第一行包含两个整数,一个整数 $N$ $(3\leq N\leq 2\times 10^5)$ 表示点的数量 ,一个整数 $K$ $(1\leq K\leq N)$ 表示起点的编号 。 接下来 $N$ 行,每行两个整数 $A_i$ , $B_i$ $(-10^6\leq A_i,B_i\leq10^6)$ 表示第 $i$ 个点的坐标 。 ### 输出格式 一个整数,表示最小移动路径的长度,误差不超过 $10^{-6}$ 。

加入题单

上一题 下一题 算法标签: