Booster

题目描述

在一个二维平面上，有 $N$ 个城镇和 $M$ 个宝箱。城镇 $i$ 的坐标为 $(X_i,Y_i)$，宝箱 $i$ 的坐标为 $(P_i,Q_i)$。 Takahashi 将进行一次旅行，他从原点出发，访问所有 $N$ 个城镇，然后返回原点。
访问宝箱不是强制的，但每个宝箱里都包含一个加速器。每次他拾取一个加速器，他的移动速度会乘以 $2$。 Takahashi 的初始移动速度为 $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)$, and $(P_i,Q_i)$ are distinct. All values in the input are integers.这里给出一种完成旅行的最优方式。

从原点以速度 $1$ 前往宝箱 $1$，距离为 $1$，耗时为 $1$。 从宝箱 $1$ 以速度 $2$ 前往城镇 $1$，距离为 $1$，耗时为 $0.5$。 从城镇 $1$ 以速度 $2$ 前往城镇 $2$，距离为 $1$，耗时为 $0.5$。 从城镇 $2$ 以速度 $2$ 返回原点，距离为 $1$，耗时为 $0.5$。
这里给出另一种完成旅行的最优方式。

从原点以速度 $1$ 前往城镇 $1$，距离为 $1.41\ldots$，耗时为 $1.41\ldots$。 从城镇 $1$ 以速度 $1$ 前往城镇 $2$，距离为 $1$，耗时为 $1$。 从城镇 $2$ 以速度 $1$ 返回原点，距离为 $1$，耗时为 $1$。
这里给出另一种完成旅行的最优方式。

从原点以速度 $1$ 前往宝箱 $1$，距离为 $1$，耗时为 $1$。 从宝箱 $1$ 以速度 $2$ 前往宝箱 $2$，距离为 $1.41\ldots$，耗时为 $0.707\ldots$。 从宝箱 $2$ 以速度 $4$ 前往城镇 $1$，距离为 $5$，耗时为 $1.25$。 从城镇 $1$ 以速度 $4$ 返回原点，距离为 $5.65\ldots$，耗时为 $1.41\ldots$。

标签: AtCoder|abc274E

来源

AtCoder|abc274E