#geocon2013b. [geocon2013_b]玉座の間
[geocon2013_b]玉座の間
题目描述
你是一个富饶的王国的统治者,你从双亲那继承了这个绿水青山环绕着小王国。
在继承王位之前,你打算改造一下王座。
强迫症非常严重的你发现家具们的位置左右不对称。
但是,把家具们移来移去很费改装费。
你要最小化把家具移至左右对称时搬运的总距离。
把家具视为二维空间上的一个点。家具无种类区别,互不区分。
+++++++++++++++++++++++++++++++++
所谓的左右对称状态,指的就是以y轴为对称轴翻转这些点后的状态与原来的状态相同。
比如,以(-1,0),(0,0),(1,0)为例,被翻转后变成了(-1,0),(0,0),(1,0)。因为前后两者是同样的状态,所以是左右对称。
但是,以(-1,0),(1,0),(1,0)为例,被翻转后变成了(-1,0),(-1,0),(1,0)。因为前后两者状态不一致,所以不是左右对称。
家具不论怎么分布都能被搬动,就算多个家具重叠在一起也没关系。
+++++++++++++++++++++++++++++++++
输入格式:
N
X1 Y1
X2 Y2
...
XN YN
+++++++++++++++++++++++++++++++++
第一行表示家具的数目,N是整数。
第二行开始的N+1行是表示家具坐标的整数Xi Yi (1 ≦ i ≦ N , −1000 ≦ Xi,Yi ≦ 1000)
所有给出的家具坐标都不同,即, 满足i ≠ j,且 (Xi,Yi) ≠ (Xj,Yj)
+++++++++++++++++++++++++++++++++
输出格式:
输出为了使家具左右对称,移动家具所耗费的最小距离总和。
可以输出小数点以后任意位数,绝对误差或相对误差达到10^-6以下视为正确答案。
+++++++++++++++++++++++++++++++++
输入输出样例
输入样例#1:
1
1 0
+++++++++++++++++++++++++++++++++
输出样例#1:
1.0000000
+++++++++++++++++++++++++++++++++
输入样例#2:
3
-1 0
0 0
1 0
+++++++++++++++++++++++++++++++++
输出样例#2:
0.0000000
+++++++++++++++++++++++++++++++++
输入样例#3:
2
2 2
-2 1
+++++++++++++++++++++++++++++++++
输出样例#3:
1.0000000
+++++++++++++++++++++++++++++++++
输入样例#4:
8
2 2
7 1
9 -4
-10 1
-6 -9
-6 10
8 8
2 -4
+++++++++++++++++++++++++++++++++
输出样例#4:
15.6593790
+++++++++++++++++++++++++++++++++
部分分
这个问题分为1-4四个部分的分,各满足以下的条件:
(1) 50分 : N = 1 N\ =\ 1 N = 1
(2) 50分 : 1 ≦ N ≦ 10 1\ ≦\ N\ ≦\ 10 1 ≦ N ≦ 10
(3) 50分 : 1 ≦ N ≦ 20 1\ ≦\ N\ ≦\ 20 1 ≦ N ≦ 20
(4) 50分 : 1 ≦ N ≦ 100 1\ ≦\ N\ ≦\ 100 1 ≦ N ≦ 100
+++++++++++++++++++++++++++++++++
样例解释2:
已经左右对称的家具不需要移动。
+++++++++++++++++++++++++++++++++
样例解释3:
假如把家具从案例3中给出的两个坐标移至(2,1.5)和(-2,1.5),那么总的移动距离为1。