問題文
众所周知,宇宙自大爆炸诞生以来一直在膨胀。
天文学家高桥决定测量宇宙的膨胀率。
高桥君在那里。 2 每天都一样 我们观察了 N 恒星的位置。恒星的位置被记录为坐标平面上的一个点。也就是说,每一天的观测结果都在坐标平面上。 它变成由 N 点组成的点集。 比较
2 观测结果,我们发现1 对于作为第二次观察结果的点集,以下 3 依次执行两个操作 2 我们发现它与第二次观察结果的点集相匹配。
- 以相同方向和相同距离平移。
- 绕原点旋转相同角度。
- 以原点为中心 与 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 移至观测结果的点集。
- x 轴向 -0.5、 y 轴向 -0.5 平行移动。
- 以原点为中心,45° 顺时针旋转。
- 以原点为中心 与 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