分数: 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}.
示例输入 1
2 1 1 1 0 1 1 0
示例输出 1
2.5000000000
这是完成旅程的一种最佳方式。
- 走得远 1 从原点到宝箱 1 速度为 1,花费时间 1.
- 走得远 1 从胸部 1 到镇 1 速度为 2,花费时间 0.5.
- 走得远 1 来自城镇 1 到镇 2 速度为 2,花费时间 0.5.
- 走得远 1 来自城镇 2 到原点的速度为 2,花费时间 0.5.
示例输入 2
2 1 1 1 0 1 100 0
示例输出 2
3.4142135624
这是完成旅程的一种最佳方式。
- 走得远 1.41\ldots 从出发地到城镇 1 速度为 1,花费时间 1.41\ldots.
- 走得远 1 来自城镇 1 到镇 2 速度为 1,花费时间 1.
- 走得远 1 来自城镇 2 到原点的速度为 1,花费时间 1.
示例输入 3
1 2 4 4 1 0 0 1
示例输出 3
4.3713203436
这是完成旅程的一种最佳方式。
- 走得远 1 从原点到宝箱 1 速度为 1,花费时间 1.
- 走得远 1.41\ldots 从胸部 1 到胸部 2 速度为 2,花费时间 0.707\ldots.
- 走得远 5 从胸部 2 到镇 1 速度为 4,花费时间 1.25.
- 走得远 5.65\ldots 来自城镇 1 到原点的速度为 4,花费时间 1.41\ldots.