11018: NC21315 - 农村连接城市
[Creator : ]
Description
平面上有 $N$ 个城市和 $M$ 个乡村，一开始没有任何的道路
为了改善这个局面，主席决定采取一些策略使得每个乡村都能连接到至少一个城市
当存在一个乡村与任何城市都没有联系时，执行如下操作
1：随机挑选一个未联系的乡村 $V$
2：选择离V最近（欧几里得距离）的一个已链接城市的乡村或者城市，如果有多个，满足条件的点，随机选择，假设选择的点为 $P$
3：在 $V$ 与 $P$ 之间建设一条道路
求期望需要修建多长的道路能使得所有的乡村都能直接或者间接的连接到城市
为了改善这个局面，主席决定采取一些策略使得每个乡村都能连接到至少一个城市
当存在一个乡村与任何城市都没有联系时，执行如下操作
1：随机挑选一个未联系的乡村 $V$
2：选择离V最近（欧几里得距离）的一个已链接城市的乡村或者城市，如果有多个，满足条件的点，随机选择，假设选择的点为 $P$
3：在 $V$ 与 $P$ 之间建设一条道路
求期望需要修建多长的道路能使得所有的乡村都能直接或者间接的连接到城市
Input
第一行输入两个整数 $n,m\ (1 ≤ n ≤ 50, 1 ≤ m ≤ 50)$
接下来一行输入 $n$ 个整数 cityX[i] 表示第 $i$ 个城市的 $x$ 坐标
接下来一行输入 $n$ 个整数 cityY[i] 表示第 $i$ 个城市的 $y$ 坐标
接下来一行输入 $m$ 个整数 villageX[i] 表示第 $i$ 个乡村的 $x$ 坐标
接下来一行输入 $m$ 个整数 villageY[i] 表示第 $i$ 个乡村的 $y$ 坐标
所有的点的坐标都是唯一的所有坐标的值都在 $0$ 到 $1,000,000$ 以内
接下来一行输入 $n$ 个整数 cityX[i] 表示第 $i$ 个城市的 $x$ 坐标
接下来一行输入 $n$ 个整数 cityY[i] 表示第 $i$ 个城市的 $y$ 坐标
接下来一行输入 $m$ 个整数 villageX[i] 表示第 $i$ 个乡村的 $x$ 坐标
接下来一行输入 $m$ 个整数 villageY[i] 表示第 $i$ 个乡村的 $y$ 坐标
所有的点的坐标都是唯一的所有坐标的值都在 $0$ 到 $1,000,000$ 以内
Output
输出一个浮点数，保留六位小数。
Sample 1 Input
1 2
3
0
3 3
2 1
Sample 1 Output
2.500000
Sample 2 Input
4 4
1 4 7 10
5 5 5 5
1 4 7 10
4 4 4 4
Sample 2 Output
4.000000
Sample 3 Input
3 3
1 2 3
4 4 4
4 5 6
4 4 4
Sample 3 Output
4.166667
HINT
牛客网。