AT_past202104_l 都市計画

[problemUrl]: https://atcoder.jp/contests/past202104-open/tasks/past202104_l ある都市には、タワー $ 1 $ からタワー $ N $ までの $ N $ 個のタワーと、環状交差点 $ 1 $ から 環状交差点 $ M $ までの $ M $ 個の環状交差点があります。 この都市は半径 $ 10^9 $ メートルの円の形をしています。この円の中心にあたる地点から東に $ x $ メートル、北に $ y $ メートル進んだ地点を地点 $ (x,\ y) $ と表すことにします。 タワー $ i $ は地点 $ (\mathrm{PX}_i,\ \mathrm{PY}_i) $ に建っています。 環状交差点 $ i $ は地点 $ (\mathrm{CX}_i,\ \mathrm{CY}_i) $ を中心とする半径 $ R_i $ メートルの円 (内部は含まない) の形をしています。 高橋君は、以下の条件を満たすようにこの都市に線分状の道路をいくつか追加します。 - 追加される道路の端点は全て、$ N $ 個のタワーの建っている地点のうちいずれかに一致するか、$ M $ 個の環状交差点のいずれかの上に乗っている - 以下のルールに従って、どの $ 2 $ つのタワーが建っている地点も互いに行き来可能である - 今いる地点が、ある環状交差点の上にあるとき、その環状交差点上の任意の地点に移動できる - 今いる地点が、ある道路の端点であるとき、その道路の他方の端点に移動できる **(移動は端点から端点に限ることに注意せよ)** - これ以外の移動は許されない 追加される道路の長さの合計として考えられる最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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} $ 以下であるとき正解と判定される。

### 注意 この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \le\ N\ \le\ 50 $ - $ 1\ \le\ M\ \le\ 8 $ - $ 0\ \le\ \mathrm{PX}_i\ \le\ 1000 $ - $ 0\ \le\ \mathrm{PY}_i\ \le\ 1000 $ - $ i\ \neq\ j $ ならば $ (\mathrm{PX}_i,\ \mathrm{PY}_i)\ \neq\ (\mathrm{PX}_j,\ \mathrm{PY}_j) $ - $ 0\ \le\ \mathrm{CX}_i\ \le\ 1000 $ - $ 0\ \le\ \mathrm{CY}_i\ \le\ 1000 $ - $ 1\ \le\ R_i\ \le\ 1000 $ - $ i\ \neq\ j $ ならば $ (\mathrm{CX}_i,\ \mathrm{CY}_i,\ R_i)\ \neq\ (\mathrm{CX}_j,\ \mathrm{CY}_j,\ R_j) $ - 入力に含まれる値は全て整数 ### Sample Explanation 1 各タワーと環状交差点の配置は下図のようになっています。 !\[\](https://img.atcoder.jp/past202104/70ffd4874808032c5c57f53fdabbd4a8.png) 例えば以下の $ 2 $ つの道路を追加すると条件を満たします。 - $ (0,\ 0) $ と $ (1,\ 0) $ を結ぶ線分状の道路 - $ (5,\ 0) $ と $ (6,\ 0) $ を結ぶ線分状の道路 このとき、追加された道路の長さの和は $ 2 $ であり、これが最小です。 ### Sample Explanation 2 各タワーと環状交差点の配置は下図のようになっています。 !\[\](https://img.atcoder.jp/past202104/18299e958b01610e07dc58b413b73cfb.png) 以下の $ 3 $ つの道路を追加するのが最適な追加方法です。 - $ (0,\ 1) $ と $ (0,\ 2) $ を結ぶ線分状の道路 - $ (0,\ -2) $ と $ (0,\ -3) $ を結ぶ線分状の道路 - $ (\frac{16\ \sqrt{17}}{17},\ 1\ +\ \frac{4\ \sqrt{17}}{17}) $ と $ (4,\ 2) $ を結ぶ線分状の道路 ### Sample Explanation 3 各タワーと環状交差点の配置は下図のようになっています。 !\[\](https://img.atcoder.jp/past202104/5cb78063bd44131bd78ef88726db263c.png)