[ABC274E] Booster

### 题目描述 在平面直角坐标系中，有 $n$ 个城镇和 $m$ 个箱子。 你现在在 $(0,0)$，速度为 $1$，你需要走遍所有城镇后回到 $(0,0)$。 你可以选择走到箱子所处的位置，如果你第一次走到这个箱子，你可以吞下箱子里仅剩的一颗能量球，然后你的速度就翻倍了。 求从 $(0,0)$ 走遍所有城镇后回到 $(0,0)$ 所需的最短时间。 ### 输入格式 第一行两个整数 $n,m$，含义如题中所述。 接下来 $n$ 行，第 $i+1$ 行两个整数表示第 $i$ 个城镇的坐标 $(x_i,y_i)$。 接下来 $m$ 行，第 $i+n+1$ 行两个整数表示第 $i$ 个箱子的坐标 $(p_i,q_i)$。 ### 输出格式 一行一个小数，表示答案。 ### 数据范围与提示 样例一：路径为 $O-Chest_1-Town_1-Town_2-O$。 样例二：路径为 $O-Town_1-Town_2-O$。 **数据范围：** 对于所有数据，$1\leq n\leq 12,0\leq m\leq 5,0\leq |x_i|,|y_i|,|p_i|,|q_i|\leq 10^9$。 Translate by Zek3L.

[problemUrl]: https://atcoder.jp/contests/abc274/tasks/abc274_e $ 2 $ 次元平面上に $ N $ 個の街と $ M $ 個の宝箱があります。街 $ i $ は座標 $ (X_i,Y_i) $ に、宝箱 $ i $ は座標 $ (P_i,Q_i) $ にあります。 高橋君は原点を出発し、$ N $ 個の街全てを訪れたのち原点に戻る旅行をしようと考えています。 宝箱を訪れる必要はありませんが、宝箱の中にはそれぞれブースターが $ 1 $ つあり、ブースターを拾うごとに移動速度が $ 2 $ 倍になります。 高橋君の最初の移動速度が単位時間あたり $ 1 $ であるとき、旅行にかかる時間の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_N $ $ Y_N $ $ P_1 $ $ Q_1 $ $ \vdots $ $ P_M $ $ Q_M $

答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば正解として扱われる。

2 1
1 1
0 1
1 0

2.5000000000

2 1
1 1
0 1
100 0

3.4142135624

1 2
4 4
1 0
0 1

4.3713203436

### 制約 - $ 1\ \leq\ N\ \leq\ 12 $ - $ 0\ \leq\ M\ \leq\ 5 $ - $ -10^9\ \leq\ X_i,Y_i,P_i,Q_i\ \leq\ 10^9 $ - $ (0,0),(X_i,Y_i),(P_i,Q_i) $ は相異なる - 入力は全て整数 ### Sample Explanation 1 以下のように移動するのが最適解の一つです。 - 原点から宝箱 $ 1 $ までの距離 $ 1 $ を速さ $ 1 $ で移動する。時間が $ 1 $ かかる - 宝箱 $ 1 $ から街 $ 1 $ までの距離 $ 1 $ を速さ $ 2 $ で移動する。時間が $ 0.5 $ かかる - 街 $ 1 $ から街 $ 2 $までの距離 $ 1 $ を速さ $ 2 $ で移動する。時間が $ 0.5 $ かかる - 街 $ 2 $から原点までの距離 $ 1 $ を速さ $ 2 $ で移動する。時間が $ 0.5 $ かかる ### Sample Explanation 2 以下のように移動するのが最適解の一つです。 - 原点 から街 $ 1 $ までの距離 $ 1.41\ldots $ を速さ $ 1 $ で移動する。時間が $ 1.41\ldots $ かかる - 街 $ 1 $ から街 $ 2 $ までの距離 $ 1 $ を速さ $ 1 $ で移動する。時間が $ 1 $ かかる - 街 $ 2 $ から原点までの距離 $ 1 $ を速さ $ 1 $ で移動する。時間が $ 1 $ かかる ### Sample Explanation 3 以下のように移動するのが最適解の一つです。 - 原点から宝箱 $ 1 $ までの距離 $ 1 $ を速さ $ 1 $ で移動する。時間が $ 1 $ かかる - 宝箱 $ 1 $ から宝箱 $ 2 $ までの距離 $ 1.41\ldots $ を速さ $ 2 $ で移動する。時間が $ 0.707\ldots $ かかる - 宝箱 $ 2 $ から街 $ 1 $ までの距離 $ 5 $ を速さ $ 4 $ で移動する。時間が $ 1.25 $ かかる - 街 $ 1 $ から原点までの距離 $ 5.65\ldots $ を速さ $ 4 $ で移動する。時間が $ 1.41\ldots $ かかる