当前没有测试数据。

E - Booster

得分：500

问题描述

在一个二维平面上，有$N$个城镇和$M$个宝箱。第$i$个城镇位于坐标$(X_i,Y_i)$，第$i$个宝箱位于坐标$(P_i,Q_i)$。

高濑将进行一次旅行，在原点出发，访问所有的$N$个城镇，然后返回原点。
不一定要访问宝箱，但每个宝箱里都有一个加速器。每次拿到加速器后，他的移动速度将乘以2。

高濑的初始移动速度为1。找出完成旅行所需的最短时间。

约束

• $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)$ 是两两不同的点。
• 输入中的所有值都是整数。

输入

输入数据从标准输入读取，格式如下：

$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

• 以下是完成旅行的最优方式之一：
• 以速度$1$从原点走$1$的距离到宝箱$1$，用时$1$。
• 以速度$2$从宝箱$1$走$1$的距离到城镇$1$，用时$0.5$。
• 以速度$2$从城镇$1$走$1$的距离到城镇$2$，用时$0.5$。
• 以速度$2$从城镇$2$走$1$的距离回到原点，用时$0.5$。

2 1
1 1
0 1
100 0

3.4142135624

• 以下是完成旅行的最优方式之一：
• 以速度$1$从原点走$1.41\ldots$的距离到城镇$1$，用时$1.41\ldots$。
• 以速度$1$从城镇$1$走$1$的距离到城镇$2$，用时$1$。
• 以速度$1$从城镇$2$走$1$的距离回到原点，用时$1$。

1 2
4 4
1 0
0 1

4.3713203436

• 以下是完成旅行的最优方式之一：
• 以速度$1$从原点走$1$的距离到宝箱$1$，用时$1$。
• 以速度$2$从宝箱$1$走$1.414\ldots$的距离到宝箱$2$，用时$0.707\ldots$。
• 以速度$4$从宝箱$2$走$5$的距离到城镇$1$，用时$1.25$。
• 以速度$4$从城镇$1$走$5.656\ldots$的距离回到原点，用时$1.41\ldots$。