分数: 6 点
警告
2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
在某些城市,有 N 塔称为塔 1 直通塔 N 和 M 交通圈称为交通圈 1 穿过交通环岛 M.
该镇呈圆形,半径为 10^9 米。让 (x, y) 代表的点是 x 米东和 y 米。
塔 i 位于 (\mathrm{PX}_i, \mathrm{PY}_i).
交通圈 i 的形状为半径为 R_i 米以 (\mathrm{CX}_i, \mathrm{CY}_i) (不包括内饰)。
在这座城市中,高桥将修建一定数量的道路,每条道路均呈线段形状,以满足以下条件:
- 每条道路的每个端点都是其中一个点 N 塔矗立或位于其中之一 M 交通圈。
- 可以通过以下方式在每对塔之间移动:
- 如果您现在位于某个交通圈内,您可以到达该交通圈内的任何地方;
- 如果您现在位于某条道路的一个端点,您可以到达该道路的另一个端点 (但不是中间点);
- 不允许进行其他类型的移动。
求所建道路的最小可能总长度。
约束
- 2 \le N \le 50
- 1 \le M \le 8
- 0 \le \mathrm{PX}_i \le 1000
- 0 \le \mathrm{PY}_i \le 1000
- (\mathrm{PX}_i, \mathrm{PY}_i) \neq (\mathrm{PX}_j, \mathrm{PY}_j) 为 i \neq j
- 0 \le \mathrm{CX}_i \le 1000
- 0 \le \mathrm{CY}_i \le 1000
- 1 \le R_i \le 1000
- (\mathrm{CX}_i, \mathrm{CY}_i, R_i) \neq (\mathrm{CX}_j, \mathrm{CY}_j, R_j) 为 i \neq j
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
\mathrm{PX}_1 \mathrm{PY}_1
\mathrm{PX}_2 \mathrm{PY}_2
\mathrm{PX}_3 \mathrm{PY}_3
\hspace{22pt} \vdots
\mathrm{PX}_N \mathrm{PY}_N
\mathrm{CX}_1 \mathrm{CY}_1 R_1
\mathrm{CX}_2 \mathrm{CY}_2 R_2
\mathrm{CX}_3 \mathrm{CY}_3 R_3
\hspace{33pt} \vdots
\mathrm{CX}_M \mathrm{CY}_M R_M
输出
打印答案。 当您的输出与我们的答案的绝对或相对误差最多为 10^{-5}.
示例输入 1
2 1 0 0 6 0 3 0 2
示例输出 1
2.00000000000
塔楼和交通环岛位于以下位置:

我们可以通过建设以下两条道路来满足条件:
- 一条线段形状的道路连接 (0, 0) 和 (1, 0);
- 一条线段形状的道路连接 (5, 0) 和 (6, 0).
此处,已修建道路的总长度为 2,这是可能的最小总和。
示例输入 2
2 2 4 2 0 1 0 0 2 0 1 4
示例输出 2
2.12310562562
塔楼和交通环岛位于以下位置:

建设以下3条道路为最佳:
- 一条连接的道路 (0, 1) 和 (0, 2);
- 一条连接的道路 (0, -2) 和 (0, -3);
- 一条连接的道路 (\frac{16 \sqrt{17}}{17}, 1 + \frac{4 \sqrt{17}}{17}) 和 (4, 2).
示例输入 3
3 4 9 2 5 20 0 21 0 0 2 0 0 10 16 0 10 10 15 3
示例输出 3
13.10603728957
塔楼和交通环岛位于以下位置: