← 返回题目列表

Codeforces · 671/A

A. 回收瓶子

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

今天是 Kekoland 的回收日。为了庆祝这一节日,阿迪尔和贝拉去了中央公园公园,在那里他们可以从地上捡起瓶子,然后把它们放进回收箱。

我们可以将 Central Perk 视为坐标平面。地面上有n个瓶子,第i个瓶子位于位置(xi,yi)。阿迪尔和贝拉一次只能携带一瓶。

对于 Adil 和 Bera,流程如下所示:

1. 选择停止或继续收集瓶子。
2. 如果选择继续,则选择一些瓶子并向其走去。
3. 拿起这个瓶子,然后走到回收站。
4. 转到步骤 1。

阿迪尔和贝拉可以独立移动。允许他们同时拾取瓶子,两个人中的任何一个都可以拾取所有瓶子,允许其中一个保持静止,而另一个继续拾取瓶子。

他们希望组织这个过程,使他们行走的总距离(Adil 行走的距离和 Bera 行走的距离之和)尽可能最小。当然,最后所有瓶子都应该放入回收箱中。

输入

输入的第一行包含六个整数 ax、ay、bx、by、tx 和 ty(0 ≤ ax、ay、bx、by、tx、ty ≤ 109)——分别是 Adil、Bera 和回收箱的初始位置。

第二行包含一个整数 n (1 ≤ n ≤ 100 000) — 地面上的瓶子数量。

接下来n行,每行包含两个整数xi和yi (0 ≤ xi, yi ≤ 109)——第i个瓶子的位置。

保证Adil、Bera、回收箱和所有瓶子的位置是不同的。

输出

打印一个实数——阿迪尔和贝拉将所有瓶子放入回收箱所需步行的最小可能总距离。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

3 1 1 2 0 0
3
1 1
2 1
2 3

输出 #1

11.084259940083

输入 #2

5 0 4 2 2 0
5
5 2
3 0
5 5
3 5
3 3

输出 #2

33.121375178000

注意

考虑第一个样本。

Adil 将使用以下路径:$$(3,1)\rightarrow(2,1)\rightarrow(0,0)\rightarrow(1,1)\rightarrow(0,0)$$。

Bera 将使用以下路径:$$(1,2)\rightarrow(2,3)\rightarrow(0,0)$$。

Adil 的路径长度为 $$1 + \sqrt{5} + \sqrt{2} + \sqrt{2}$$ 单位,而 Bera 的路径长度为 $$\sqrt{2} + \sqrt{13}$$ 单位。