D - Big Bang Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

宇宙はビッグバンによって誕生して以来、膨張し続けていることが知られています。

天文学者である高橋君はその宇宙の膨張の速度を計測することにしました。

高橋君はある 2 つの日について、同じ N 個の星の位置を観測しました。星の位置は座標平面上の点として記録されます。つまり各日の観測結果は座標平面上の N 個の点からなる点集合になります。

2 回の観測の結果を見比べてみると、1 回目の観測結果である点集合に対して以下の 3 つの操作を順に実行すると 2 回目の観測結果である点集合に一致することがわかりました。

  1. 同じ向きに同じ距離だけ平行移動する。
  2. 原点を中心に同じ角度だけ回転する。
  3. 原点を中心に P 倍 (1 ≦ P) に相似拡大する。つまり点 (a, b) を点 (a×P, b×P) に移すという操作をすべての点に実行する。

ここで P の値がわかれば膨張速度を求めることができそうです。

いざ P を求めようとした高橋君でしたが、うっかりどの点がどの星に対応するのか記したデータをなくしてしまいました。

そこで高橋君は優秀なプログラマーであるあなたに助けを借りることにしました。

1 回目と 2 回目の観測結果が与えられるので P を求めてください。

入力

入力は以下の形式で標準入力から与えられる

N
Ax_1 Ay_1
Ax_2 Ay_2
:
Ax_N Ay_N
Bx_1 By_1
Bx_2 By_2
:
Bx_N By_N
  • 1 行目には高橋君が観測した星の個数 N (2 ≦ N ≦ 10^5) が与えられる。
  • 2 行目からの N 行のうち i 行目には 1 回目に観測された i 番目の星の位置の x 座標と y 座標の値を表す 2 つの整数 Ax_i, Ay_i (-15,000 ≦Ax_i, Ay_i ≦ 15,000) が空白区切りで与えられる。
  • N+2 行目からの N 行のうち i 行目には 2 回目に観測された i 番目の星の位置の x 座標と y 座標の値を表す 2 つの整数 Bx_i, By_i (-10^9 ≦Bx_i, By_i ≦ 10^9) が空白区切りで与えられる。
  • 1 回目も 2 回目も、同じ点に複数の星が観測されることはない。
  • 1 回目に観測された i 番目の星と 2 回目に観測された i 番目の星が同一の星とは限らない。

部分点

この問題には部分点が設定されている。

  • 1 ≦ N ≦ 3,000を満たすデータセットに正解した場合は 50 点が与えられる。
  • 1 ≦ N ≦ 10^5を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。

出力

P の値を 1 行に出力せよ。 出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-6} 以下であれば許容される。出力の末尾にも改行を入れること。

入力例1

4
0 0
0 1
1 0
1 1
0 2
2 0
-2 0
0 -2

出力例1

2.8284271247

以下のように操作を実行すれば、 1 回目の観測結果の点集合が、 2 回目の観測結果の点集合に移されます。

  1. x 軸方向に -0.5、 y 軸方向に -0.5 平行移動させる。
  2. 原点を中心にして、45° 時計回りに回転させる。
  3. 原点を中心に 2√2 倍する。

よって P = 2√2 となります。

入力例2

6
3 4
1 3
4 3
2 2
0 1
2 0
5 5
-1 2
-1 -3
2 1
2 6
4 -3

出力例2

2.2360679775