题目描述
小明正在玩《文明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
提示