← 返回题目列表

AtCoder · geocon2013_b

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 给出。
  • 从第2行到第N+1行是代表家具坐标的整数。 Xi Yi (1 ≦ i ≦ N , -1000 ≦ Xi,Yi ≦ 1000) 用空格分隔。
  • 所有给定的家具坐标都不同。也就是说,i ≠ j 如果 (Xi,Yi) ≠ (Xj,Yj) 满意。

出力

输出使家具对称所需的总移动距离的最小值。
可以输出小数点后任意位数,且绝对误差和相对误差至少其中之一为10。-6以下任何答案都被认为是正确的。

部分点

该问题分为子点(1)至(4),每个子点满足以下条件。

  • (1) 50点 : N = 1
  • (2) 50点 : 1 ≦ N ≦ 10
  • (3) 50点 : 1 ≦ N ≦ 20
  • (4) 50点 : 1 ≦ N ≦ 100

入力例 1

1
1 0

出力例 1

1.0000000

最优将家具移动到(0,0),移动的总距离为1。


入力例 2

3
-1 0
0 0
1 0

出力例 2

0.0000000

无需移动家具,因为它已经是对称的。


入力例 3

2
2 2
-2 1

出力例 3

1.0000000

例如,如果将家具移动到 (2,1.5),(-2,1.5),则移动的总距离将为 1。


入力例 4

8
2 2
7 1
9 -4
-10 1
-6 -9
-6 10
8 8
2 -4

出力例 4

15.6593790