あらすじ
チノちゃんたちは、都会に旅行に来ていた。 そのうちの1日だけ、チノちゃんは1人で行動することになった。
しかし携帯の充電を忘れてしまい、地図を見るも自分の場所がわからず迷子になってしまった。 いっそのこと自分から迷ってしまおうと覚悟を決めたチノちゃん、いろんな人に道を聞きながら旅をすることに。 そのうち何人かにおすすめの場所を教えてもらい、そこを順番に回ることにした。
問題
最初チノちゃんは座標(0 , 0)の位置にいる(近くの人に教えてもらった)。 出会った人N人におすすめの場所の座標(x , y)を教えてもらった。 チノちゃんは体力があまりないので、なるべく短い距離で全ての場所を訪れたい。 教えてもらった場所を全て訪れて、座標(1000 , 1000)の位置にあるホテル"ロイヤル・キャッツ"に戻るまでの最短距離を求めよう。 チノちゃんは最短の直線距離で移動できるものとする。
入力
入力は以下の形式で標準入力から与えられる。
N x1 y1 x2 y2 : xn yn
出力
求めた距離を1行で出力する。 誤差は1e-5まで許容される。
制約
- 0 < N ≤ 16
- 0 < xi , yi < 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
うろうろ。