这是官方题解的中文 AI 翻译

第 1 组

实现朴素解法：对于每个询问，枚举所有点对，复杂度为 $O(n^2 \cdot q)$。

第 2-3 组

注意到，距离最远的点对必然在原点集的凸包上。由于凸包在所有询问中不变，可以用整数运算 $O(n^2)$ 预处理出凸包。

然后，对于每个询问，可以用标准算法在凸多边形上找出最远点对。可以用旋转卡壳法 $O(n)$ 求解，或者 $O(n \log n)$ 对每条边找不超过两个最远的点，通过寻找与该边平行的切线并用这些点与边上的点配对更新答案。

第 4-5 组

由于所有点都是随机的，凸包大小为 $O(\log n)$。在第 4 组，可以在构造凸包后直接用第 1 组的朴素做法；在第 5 组，只需用第 2-3 组的方法，并用 $O(n \log n)$ 构造凸包即可。

下面讨论接近完整解法的思路：

设原点集的凸包为 $A$。可以证明，原点集中距离最远的两点的距离，就是从原点到集合 $B$ 上某点的最大距离，其中 $B$ 是 Minkowski 和 $A + (-A)$。注意，若将 $A$ 按比例 $\alpha$ 拉伸，则 $B$ 也会按 $\alpha$ 拉伸。因此，问题转化为：给定 $O(n)$ 个点对 $(x, y)$，对于每个询问，计算 $\max_{(x, y) \in B} \sqrt{x^2 \alpha^2 + y^2}$，即 $\sqrt{\max_{(x, y) \in B} (x^2 \alpha^2 + y^2)}$。这就转化为求一组线性函数中的最大值，可以用凸包技巧（convex hull trick）在 $O(q \log n)$ 时间内解决。

第 6-7 组

在这些组中，需要将所有线性函数集合分组，利用每条边最远的 $1-2$ 个点不会因平面拉伸而改变。其本质原因是：对平面等比拉伸，向量的叉积符号不变。

然后，对这些线性函数集合构建凸包，并用二分查找回答每个询问。

总复杂度为 $O(n^2 + (n + q) \log n)$。

第 8-9 组

完整做法需要在接近线性时间内构建所有线性函数集合，然后用第 6-7 组的方法处理。

最终复杂度为 $O((n + q) \log(n + q))$，可以获得 $100$ 分，并且除了在线性函数集合中找最优值外，无需进行任何实数运算。