B - 玉座の間 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたは、両親から引き継いだ、川と緑に囲まれた小さいながらも豊かな王国の統治者です。
王位を引き継ぐにあたって玉座の間の改装を行うことにしました。
とても几帳面なあなたは家具が左右対称になっていないと気がすみません。
しかし、家具をあちこち移動させていると改装費がかさんでしまいます。
あなたは家具を左右対称になるように動かす時の、家具の移動距離の合計を最小化することにしました。

家具は2次元上の点として考えます。家具には種類がなく、区別しません。
左右対称な状態とは、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
  • 1行目には家具の数を表す整数 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