P13545 [OOI 2022] Plane stretching

Igor 是一位几何学爱好者，他为自己买了一张平面和一组 $P$，包含 $n$ 个不同的点，第 $i$ 个点坐标为 $(x_i, y_i)$。 他很快就能找出这组点中距离最远的两点。很快他觉得这太简单了，于是想出 $q$ 个实数 $\alpha_1, \alpha_2, \ldots, \alpha_q$。对于每一个 $\alpha_j$，Igor 都想知道：如果将所有点的 $x$ 坐标按 $\alpha_j$ 缩放后，点集中最远的两点间的最大距离是多少。形式化地说，他关心集合 $(x_i \cdot \alpha_j, y_i)$ 中最远两点的距离。请你帮帮 Igor！

每组输入包含多组测试数据。第一行包含两个整数 $t$ 和 $g$（$1 \leq t \leq 250\,000$，$0 \leq g \leq 9$），分别表示测试数据组数和当前测试组编号（用于指示额外限制）。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 500\,000$，$1 \leq q \leq 500\,000$），分别表示点的数量和查询的数量。 接下来的 $n$ 行，每行两个整数 $x_i$ 和 $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$），表示每个点的坐标。保证同一组内所有点互不相同。 接下来的 $q$ 行，每行一个实数 $\alpha_j$（$1 \leq \alpha_j \leq 10^9$），表示一次缩放的系数。 记所有测试数据中 $n_i$ 的和为 $N$，所有 $q_i$ 的和为 $Q$。保证 $N, Q \leq 500\,000$。

对于每组测试数据，输出 $q$ 个实数，第 $i$ 个为对应查询的答案。 你的答案只要绝对误差或相对误差不超过 $10^{-6}$ 即可。更具体地说，若 $a$ 为你的答案，$b$ 为标准答案，则只要 $\frac{|a-b|}{\max(b, 1)} \leq 10^{-6}$，就被认为是正确的。

### 评分说明 本题测试数据共分为 9 组。只有通过某组所有测试点，且通过所有必需的前置组，才能获得该组分数。**离线评测**表示该组的评测结果将在比赛结束后公布。 随机点表示每个坐标均独立均匀地在 $-10^9$ 到 $10^9$ 之间随机生成。 | Group | Points | $n_i$ | $N$ | $q_i$ | $Q$ | 必须通过的组 | 备注 | |:-----:|:------:|:-----:|:---:|:-----:|:---:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | -- | -- | 样例测试点 | | 1 | 12 | $n_i \leq 10$ | $N \leq 2000$ | $q_i \leq 10$ | $Q \leq 2000$ | 0 | | | 2 | 9 | $n_i \leq 2000$ | $N \leq 2000$ | $q_i \leq 2000$ | $Q \leq 2000$ | 0--1 | | | 3 | 13 | $n_i \leq 5000$ | $N \leq 5000$ | $q_i \leq 10\,000$ | $Q \leq 10\,000$ | 0--2 | | | 4 | 11 | $n_i \leq 100\,000$ | $N \leq 100\,000$ | $q_i \leq 100\,000$ | $Q \leq 100\,000$ | -- | 随机点 | | 5 | 8 | -- | -- | -- | -- | 4 | 随机点 | | 6 | 12 | $n_i \leq 5000$ | $N \leq 5000$ | $q_i \leq 100\,000$ | $Q \leq 100\,000$ | 0--3 | | | 7 | 11 | $n_i \leq 5000$ | $N \leq 5000$ | -- | -- | 0--3, 6 | | | 8 | 10 | $n_i \leq 100\,000$ | $N \leq 100\,000$ | $q_i \leq 100\,000$ | $Q \leq 100\,000$ | 0--4, 6 | | | 9 | 14 | -- | -- | -- | -- | 0--8 | **离线评测** |