#BZOJ2680. 玩游戏1
-
ID: 1145
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
玩游戏1
No submission language available for this problem.
题目描述
游戏规则是这样的：
一开始平面上有2N个点，两个人轮流进行操作，每次操作，玩家可以将一个还未占领的点占领。
最后玩家的得分为他占领的点两两之间的距离和。
小Z现决定挑战小K，为了显示自己无比NB的IQ,小Z决定让小K作为先手，而由于小K的光环过于强大，以至于小Z是屡战屡败。
于是，小Z求助与你，在两人都采取最优策略情况下，他会与小K的分数差多少呢？？
输入格式
本题有多组数据。第一行，一个正整数N,( N<=500 ) 下面2N行，每行两个数，代表这个点的坐标。
输出格式
最小差距,保留3位小数。
2
0 0
0 1
1 0
1 1
2
0 0
1 0
0 3
1 5
0.000
1.937