CF671A Recycling Bottles

在 Kekoland 的回收日，Adil 和 Bera 前往 Central Perk 庆祝，在那里他们可以把地上的瓶子捡起来放进回收箱。 我们可以将 Central Perk 视为一个坐标平面。地上有 $n$ 个瓶子，第 $i$ 个瓶子的位置为 $(x_{i},y_{i})$。Adil 和 Bera 每次只能各自携带一个瓶子。 对于 Adil 和 Bera，两人的操作如下： 1. 选择停止或继续捡瓶子。 2. 如果选择继续，则选择一个瓶子并走向它。 3. 捡起这个瓶子并走向回收箱。 4. 回到第 1 步。 Adil 和 Bera 可以独立移动，他们可以同时捡瓶子，每个瓶子可以由两人中的任何一人捡起，也允许其中一人暂停，另一个人继续捡瓶子。 他们希望安排一个流程，使得两人行走距离之和（即 Adil 的总距离与 Bera 的总距离之和）尽可能小。当然，最后所有瓶子都必须被放进回收箱。

输入的第一行包含六个整数 $a_{x}$、$a_{y}$、$b_{x}$、$b_{y}$、$t_{x}$ 和 $t_{y}$（$0 \leq a_{x},a_{y},b_{x},b_{y},t_{x},t_{y} \leq 10^{9}$），分别表示 Adil、Bera 和回收箱的初始位置。 第二行包含一个整数 $n$（$1 \leq n \leq 100000$），表示地上的瓶子数量。 接下来的 $n$ 行，每行包含两个整数 $x_{i}$、$y_{i}$（$0 \leq x_{i},y_{i} \leq 10^{9}$），表示第 $i$ 个瓶子的位置。 保证 Adil、Bera、回收箱及所有瓶子的位置均两两不同。

输出一个实数，表示 Adil 和 Bera 为将所有瓶子放进回收箱所需步行的最小总距离。只要你的答案和标准答案的绝对误差或相对误差不超过 $10^{-6}$，就会被判为正确。 即，设你的答案为 $a$，标准答案为 $b$，如果满足 $|a - b| / \max(1, |b|) \leq 10^{-6}$，则判为正确。

来看第一个样例。 Adil 将采取如下的路径：。 Bera 将采取如下的路径：。 Adil 的路径长度为 ，Bera 的路径长度为 。 由 ChatGPT 5 翻译