[AdditionalFile5381.zip](file://AdditionalFile5381.zip?type=additional_file)

#5381. 「OOI 2022 Day 2」平面拉伸

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2022 Day2 T1 「Растягивание плоскости / Plane stretching」。

伊戈尔非常热爱几何学，因此他购买了一个平面，上面标记了 $n$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。

观察这些点后，伊戈尔很快找到了距离最远的一对点。然而，这对他来说还不够，因此对于 $q$ 个数字 $\alpha_1, \alpha_2, \alpha_3, \ldots, \alpha_q$，他想知道如果将平面沿 $x$ 坐标拉伸 $\alpha_j$ 倍后，点对之间的最大距离会变成多少。

更正式地，伊戈尔有 $q$ 个查询，在第 $j$ 个查询中，对于数字 $\alpha_j$，伊戈尔希望找到由 $n$ 个点组成的新点集（坐标为 $(x_i \cdot \alpha_j, y_i)$）中距离最远的两点之间的距离。请帮助伊戈尔回答这些查询。

输入格式

每个测试点包含多组输入数据。第一行包含两个整数 $t$ 和 $g$ $(1 \leq t \leq 250000, 0 \leq g \leq 9)$，分别表示输入数据的组数和子任务编号。接下来是各组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $q$ $(2 \leq n \leq 500000, 1 \leq q \leq 500000)$，分别表示点的数量和查询的数量。

接下来的 $n$ 行描述点的坐标，每行包含两个整数 $x_i$ 和 $y_i$ $(-10^{9} \leq x_i, y_i \leq 10^{9})$，表示第 $i$ 个点的坐标。保证每组数据中所有点的坐标各不相同。

接下来的 $q$ 行描述查询，每行包含一个实数 $\alpha_j$ $(1 \leq \alpha_j \leq 10^{9})$，表示第 $j$ 个查询中 $x$ 坐标的拉伸系数。

设 $N$ 为所有数据组中 $n$ 的总和，$Q$ 为所有数据组中 $q$ 的总和。保证 $N, Q \leq 500000$。

输出格式

对于每组输入数据，输出 $q$ 行，每行包含一个实数，即第 $i$ 个查询的答案。答案被认为是正确的，如果其绝对误差或相对误差不超过 $10^{-6}$。更正式地，如果 $a$ 是你的答案，$b$ 是评委的答案，则应满足 $\frac{|a-b|}{\max(b,1)} \leq 10^{-6}$。

样例

输入

2 0
5 2
0 0
1 1
0 2
-1 3
0 4
1
2.5
8 4
0 0
6 11
7 13
4 14
0 15
-4 14
-7 13
-6 11
2
1
1.25
1.5

输出

4.000000
5.385165
28.000000
15.000000
17.500000
21.000000

在第一组输入数据中，拉伸系数为 $1$ 和 $2.5$ 时，点的分布如下：

• 拉伸系数为 $1$ 时，距离最远的点为编号 $1$ 和 $5$，坐标分别为 $(0, 0)$ 和 $(0, 4)$。
• 拉伸系数为 $2.5$ 时，距离最远的点为编号 $2$ 和 $4$，坐标分别为 $(2.5, 1)$ 和 $(-2.5, 3)$。

在第二组输入数据中，最大距离由以下点对达成：

• 第一个查询中，最大距离由编号 $3$ 和 $7$ 的点达成，坐标为 $(14, 13)$ 和 $(-14, 13)$；
• 第二个查询中，最大距离由编号 $1$ 和 $5$ 的点达成，坐标为 $(0, 0)$ 和 $(0, 15)$；
• 第三个查询中，最大距离由编号 $3$ 和 $7$ 的点达成，坐标为 $(8.75, 13)$ 和 $(-8.75, 13)$；
• 第四个查询中，最大距离由编号 $3$ 和 $7$ 的点达成，坐标为 $(10.5, 13)$ 和 $(-10.5, 13)$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。