AT_abc375_b [ABC375B] Traveling Takahashi Problem

题目描述

在二维坐标平面上的原点有高桥君。

高桥君从坐标平面上的点 $(a,b)$ 移动到点 $(c,d)$ 时，需要花费的代价为 $\sqrt{(a-c)^2+(b-d)^2}$。

请计算高桥君从原点出发，依次经过 $N$ 个点 $(X_1,Y_1),\ldots,(X_N,Y_N)$，最后返回原点时，所需的总代价。

输入格式

输入以如下格式从标准输入给出。

$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

输出格式

请输出答案。
只要与真实值的相对误差或绝对误差不超过 $10^{-6}$，即可视为正确。

输入输出样例 #1

输入 #1

2
1 2
-1 0

输出 #1

6.06449510224597979401

输入输出样例 #2

输入 #2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

输出 #2

384694.57587932075868509383

输入输出样例 #3

输入 #3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

输出 #3

1414213.56237309504880168872

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq X_i, Y_i \leq 10^9$
• 输入均为整数

样例解释 1

移动分为以下 $3$ 个阶段。

• 从 $(0,0)$ 移动到 $(1,2)$。代价为 $\sqrt{(0-1)^2+(0-2)^2} = \sqrt{5} = 2.236067977\ldots$
• 从 $(1,2)$ 移动到 $(-1,0)$。代价为 $\sqrt{(1-(-1))^2+(2-0)^2} = \sqrt{8} = 2.828427124\ldots$
• 从 $(-1,0)$ 移动回 $(0,0)$。代价为 $\sqrt{(-1-0)^2+(0-0)^2} = \sqrt{1} = 1$ 总代价为 $6.064495102\ldots$。

由 ChatGPT 4.1 翻译