← 返回题目列表

AtCoder · abc375_b

D. 高桥旅行问题

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

分数: 150 点

问题陈述

高桥位于二维坐标平面上的原点。

他从点移动的成本 (a, b) 来点 (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

求他从原点出发,访问的总成本 N 点 (X_1, Y_1), \ldots, (X_N, Y_N) 按此顺序,然后返回原点。

约束

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

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1
\vdots
X_N Y_N

输出

打印答案。
如果您的输出与真实值的绝对或相对误差最多为 10^{-6}.


示例输入 1

2
1 2
-1 0

示例输出 1

6.06449510224597979401

旅程由以下三个步骤组成:

  • 移自 (0, 0) to (1, 2)。成本是 \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
  • 移自 (1, 2) to (-1, 0)。成本是 \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
  • 移自 (-1, 0) to (0, 0)。成本是 \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

总成本为 6.064495102....


示例输入 2

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

示例输出 2

384694.57587932075868509383

示例输入 3

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

示例输出 3

1414213.56237309504880168872