Traveling Takahashi Problem

题目描述

Takahashi 在二维坐标平面的原点。 他从点 $(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}$，则将被视为正确。

2
1 2
-1 0

6.06449510224597979401

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

384694.57587932075868509383

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

1414213.56237309504880168872

提示

$1 \leq N \leq 2 \times 10^5$ $-10^9 \leq X_i, Y_i \leq 10^9$ 所有输入值均为整数。这段旅程由以下三步组成：

从 $(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$。

标签: AtCoder|abc375B

来源

AtCoder|abc375B