← 返回题目列表

AtCoder · abc022_d

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 颗恒星不一定是同一颗恒星。 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 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