AT_abc022_d.[ABC022D] Big Bang

自宇宙由宇宙大爆炸诞生以来，已知其一直在膨胀。

作为天文学家的高桥君，决定测量宇宙的膨胀速度。

高桥君在两个不同的日子里，观测了同样的 $N$ 颗星星的位置。星星的位置被记录为坐标平面上的点。也就是说，每一天的观测结果都是由 $N$ 个点组成的点集。

通过对比两次观测的结果，可以发现：对第一次观测得到的点集依次进行以下三种操作后，可以得到第二次观测的点集。

1. 沿同一方向平移相同的距离。
2. 以原点为中心旋转相同的角度。
3. 以原点为中心进行 $P$ 倍的相似放大（$1 \leq P$）。也就是说，将点 $(a, b)$ 变换为点 $(a \times P, b \times P)$，对所有点都执行此操作。

如果能够求出 $P$ 的值，就可以计算出膨胀速度。

然而，当高桥君准备求 $P$ 时，不小心丢失了记录各点对应星星的数据。

因此，他向你这位优秀的程序员寻求帮助。

给定第一次和第二次观测的结果，请你求出 $P$ 的值。

输入以如下格式从标准输入给出：

$N$
$Ax_1$ $Ay_1$
$Ax_2$ $Ay_2$
$\vdots$
$Ax_N$ $Ay_N$
$Bx_1$ $By_1$
$Bx_2$ $By_2$
$\vdots$
$Bx_N$ $By_N$

• 第 $1$ 行给出高桥君观测到的星星数量 $N$，满足 $2 \leq N \leq 10^5$。
• 接下来的 $N$ 行中，第 $i$ 行给出第一次观测到的第 $i$ 颗星的位置的 $x$ 坐标和 $y$ 坐标，分别为两个整数 $Ax_i, Ay_i$，满足 $-15,000 \leq Ax_i, Ay_i \leq 15,000$。
• 再接下来的 $N$ 行中，第 $i$ 行给出第二次观测到的第 $i$ 颗星的位置的 $x$ 坐标和 $y$ 坐标，分别为两个整数 $Bx_i, By_i$，满足 $-10^9 \leq Bx_i, By_i \leq 10^9$。
• 在第一次和第二次观测中，不会有多颗星星出现在同一个点上。
• 第一次观测到的第 $i$ 颗星和第二次观测到的第 $i$ 颗星不一定是同一颗星。

请输出 $P$ 的值，输出一行。如果输出的绝对误差或相对误差至少有一项不超过 $10^{-6}$，则视为正确。输出末尾需换行。

部分分

本题设有部分分。

• 对于满足 $1 \leq N \leq 3,000$ 的数据集，答对可得 $50$ 分。
• 对于满足 $1 \leq N \leq 10^5$ 的数据集，答对可再得 $50$ 分。总分为 $100$ 分。

样例解释 1

依次执行如下操作，可以将第一次观测的点集变换为第二次观测的点集：

1. 沿 $x$ 轴方向平移 $-0.5$，沿 $y$ 轴方向平移 $-0.5$。
2. 以原点为中心，顺时针旋转 $45^\circ$。
3. 以原点为中心放大 $2\sqrt{2}$ 倍。

因此 $P = 2\sqrt{2}$。

由 ChatGPT 4.1 翻译