B - Traveling Takahashi Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150

問題文

2 次元座標平面の原点に高橋くんがいます。

高橋くんが座標平面上の点 (a,b) から点 (c,d) に移動するには \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

移動は次の 3 行程からなります。

  • (0,0) から (1,2) に移動する。\sqrt{(0-1)^2+(0-2)^2}=\sqrt{5}=2.236067977... のコストがかかる
  • (1,2) から (-1,0) に移動する。\sqrt{(1-(-1))^2+(2-0)^2}=\sqrt{8}=2.828427124... のコストがかかる
  • (-1,0) から (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

Score : 150 points

Problem Statement

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.

Constraints

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

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}.


Sample Input 1

2
1 2
-1 0

Sample Output 1

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 Input 2

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

Sample Output 2

384694.57587932075868509383

Sample Input 3

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

Sample Output 3

1414213.56237309504880168872