Problem11239--ABC375 - B - Traveling Takahashi Problem

11239: ABC375 - B - Traveling Takahashi Problem

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point $(a, b)$ to point $(c, d)$ is $\sqrt{(a - c)^2 + (b - d)^2}$.

Find the total cost when he starts at the origin, visits $N$ points $(X_1, Y_1), \ldots, (X_N, Y_N)$ in this order, and then returns to the origin.

Input

The input is given from Standard Input in the following format:

$N$

$X_1$ $Y_1$

$\vdots$

$X_N$ $Y_N$

Output

Print the answer.
Your output will be considered correct if its absolute or relative error from the true value is at most $10^{-6}$.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $-10^9 \leq X_i, Y_i \leq 10^9$
  • All input values are integers.

Sample 1 Input

2
1 2
-1 0

Sample 1 Output

6.06449510224597979401

The journey consists of the following three steps:

  • Move from $(0, 0)$ to $(1, 2)$. The cost is $\sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977...$.
  • Move from $(1, 2)$ to $(-1, 0)$. The cost is $\sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124...$.
  • Move from $(-1, 0)$ to $(0, 0)$. The cost is $\sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1$.

The total cost is $6.064495102...$.

Sample 2 Input

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

Sample 2 Output

384694.57587932075868509383

Sample 3 Input

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

Sample 3 Output

1414213.56237309504880168872

Source/Category