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 翻译