AT_abc022_d [ABC022D] Big Bang

[problemUrl]: https://atcoder.jp/contests/abc022/tasks/abc022_d 宇宙はビッグバンによって誕生して以来、膨張し続けていることが知られています。 天文学者である高橋君はその宇宙の膨張の速度を計測することにしました。 高橋君はある $ 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 $ 番目の星が同一の星とは限らない。

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

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 3,000 $を満たすデータセットに正解した場合は $ 50 $ 点が与えられる。 - $ 1\ ≦\ N\ ≦\ 10^5 $を満たすデータセットに正解した場合はさらに $ 50 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 以下のように操作を実行すれば、 $ 1 $ 回目の観測結果の点集合が、 $ 2 $ 回目の観測結果の点集合に移されます。 1. $ x $ 軸方向に $ -0.5 $、 $ y $ 軸方向に $ -0.5 $ 平行移動させる。 2. 原点を中心にして、$ 45° $ 時計回りに回転させる。 3. 原点を中心に $ 2√2 $ 倍する。 よって $ P\ =\ 2√2 $ となります。