← 返回题目列表

AtCoder · past202104_l

L. 城市规划

中文机器翻译题面 查看原题

分数: 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

塔楼和交通环岛位于以下位置: