问题 4604 --1.文明III

4604: 1.文明III

题目描述

      小明正在玩《文明III》游戏,现在他有n个洲际导弹(简称ICBM)。他需要在最短的时间内,用这n个ICBM摧毁敌方n个目标(1个ICBM只能摧毁1个目标)。n个ICBM和目标的位置不一定相同,小明觉得给每个ICBM确定目标是一件很麻烦的事情。请你编程帮助小明给每个ICBM确定目标,使每个ICBM到其目标的距离之和最小。

输入

n   (n<=12)
第2到n+1行:x,y
说明:每一行包含一个坐标(x,y),表示一个ICBM,-10000<x,y<10000,且x,y为整数。
第n+2到2n+1行:x,y
说明:每一行包含一个坐标(x,y),表示一个目标,-10000<x,y<10000,且x,y为整数。

输出

仅一行:min
说明:min是每个ICBM到其目标距离之和的最小值。结果保留3位小数。

样例输入输出

输入#1 复制
2
1 1
-1 -1
-2 -2
2 2
输出#1 复制
2.828

提示

序号 标题 作者 发表时间 费用 订购数 操作