激活锚点
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

在一个二维平面上有 n 个传送锚点,初始时这些锚点都处于未激活状态。旅行者从某个起始坐标出发,在平面上移动。当旅行者抵达某个传送锚点时,可以将其激活。旅行者可以在任意时刻直接传送到任意一个已经激活的传送锚点。旅行者的目标是激活所有的传送锚点,求实现这一目标所需的最小移动距离(传送不计算在移动距离内)。
两点之间的距离按欧几里得距离计算,公式为 \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}

输入描述:

有多组测试数据。第一行输入一个整数 T1 \le T \le 1000)表示测试数据组数,对于每组测试数据:
第一行包含两个整数 x_0y_00 \le x_0, y_0 \le 10^6),表示旅行者的起始坐标。
第二行包含一个整数 n1 \le n \le 1000),表示传送锚点的数量。
接下来的 n 行,每行包含两个整数 x_iy_i0 \le x_i, y_i \le 10^6),表示第 i 个传送锚点的坐标。保证传送锚点的坐标两两不同。
保证所有数据 n 之和不超过 1000

输出描述:

每组数据输出一行一个数,表示激活所有传送锚点的最小移动距离。
如果相对误差或绝对误差不超过 10^{-6},您的答案将被接受。
示例1

输入

复制
1
0 0
3
2 2
3 2
2 4

输出

复制
5.828427124746190

说明

一种最优的移动路径如下图所示,旅行者从起点 S 出发,三个传送锚点分别为 A, B, C

总移动距离为 2 \sqrt{2} + 1 + 2 \approx 5.828427