021 - ひとりたび

あらすじ

チノちゃんたちは、都会に旅行に来ていた。 そのうちの1日だけ、チノちゃんは1人で行動することになった。

しかし携帯の充電を忘れてしまい、地図を見るも自分の場所がわからず迷子になってしまった。 いっそのこと自分から迷ってしまおうと覚悟を決めたチノちゃん、いろんな人に道を聞きながら旅をすることに。 そのうち何人かにおすすめの場所を教えてもらい、そこを順番に回ることにした。

問題

最初チノちゃんは座標(0 , 0)の位置にいる(近くの人に教えてもらった)。 出会った人N人におすすめの場所の座標(x , y)を教えてもらった。 チノちゃんは体力があまりないので、なるべく短い距離で全ての場所を訪れたい。 教えてもらった場所を全て訪れて、座標(1000 , 1000)の位置にあるホテル"ロイヤル・キャッツ"に戻るまでの最短距離を求めよう。 チノちゃんは最短の直線距離で移動できるものとする。

入力

入力は以下の形式で標準入力から与えられる。

N
x1 y1
x2 y2
:
xn yn

出力

求めた距離を1行で出力する。 誤差は1e-5まで許容される。

制約

• 0 < N ≤ 16
• 0 < x_i , y_i < 1000

入出力例

入力例1

2
30 30
500 500

出力例1

1414.2135623731

まっすぐ移動してるのと同じだね。

入力例2

5
532 647
231 76
198 779
114 514
95 897

出力例2

2181.9796448473

うろうろ。