HSFZPC 2026 May 4th, 2026

题目描述

Kamome 对观测流星非常感兴趣。他创建了一个无限大的二维模型来模拟流星的运动（尽管这个模型实际上并没有模拟任何东西）。 在这个模拟中有 $n$ 个流星模型，第 $i$ 个流星模型的权重是 $m_i$。每个流星模型都沿着一条固定的直线以恒定的速度运动（也可能静止）。

Kamome 已经很久没有运行这个模型了。有一天，他突然有了一个想法，并对当前的模型拍摄了两张照片。以 Kamome 的位置为原点，对于每张照片 $i$（$i=1, 2$），第 $j$ 个流星模型在平面上的位置是 $(x_{i,j}, y_{i,j})$。

你可以计算出每个流星模型的轨迹，但这还不够！Kamome 希望你计算出，在模型运行的整个过程中（你可以认为时间是无限的，包括照片拍摄之前和之后），任何其他流星模型对第 $i$ 个流星模型产生的最大引力。

注意，通常的引力公式可以重写为 $F = G \frac{m_1 m_2}{r^2}$。为了避免一些极端情况，Kamome 直接给出了 $m_i$ 作为输入，你只需要输出答案除以 $G$ 再取倒数的结果。也就是说，对于每个 $i$，你需要计算 $\min_{j \neq i} \min_{t} \frac{m_i m_j}{D_t^2(i, j)}$，其中 $D_t(i, j)$ 是在时间 $t$ 时流星模型 $i$ 和 $j$ 之间的距离，而 $t$ 可以是任意实数（负数、正数或零）。

Picture 1: Hoshizora

输入格式

每个测试包含多组数据。 第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来的测试用例描述如下。 第一行包含两个整数 $n$（$2 \le n, \sum n \le 10^5$），表示流星模型的数量。 第二行包含 $n$ 个整数 $m$（$1 \le m_i \le 100$），其定义如上所述。 接下来的 $n$ 行，每行包含四个整数 $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$（$-10^8 < x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} \le 10^8$, $0 \le |x_{1,i} - x_{2,i}|, |y_{1,i} - y_{2,i}| \le 5$），表示第 $i$ 个流星模型在两张照片中的位置。

输出格式

对于每个测试用例，输出一行 $n$ 个实数，如上所述。 假设你的答案是 $x$，陪审团的答案是 $y$，当且仅当 $\frac{|x - y|}{\max(y, 1)} < 10^{-6}$ 时，你的答案被认为是正确的。

样例

输入 1

2
2
1 2
0 0 1 0
1 1 0 1
3
1 2 3
1 0 0 -1
-1 0 0 1
0 1 1 0

输出 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

说明

对于第一个测试用例，流星模型 1 和流星模型 2 的最大引力发生在它们分别到达 $(0.5, 0)$ 和 $(0.5, 1)$ 时。此时，答案是 $\frac{m_1 m_2}{\min_{j \neq i} \min_t D_t^2(i, j)} = 2$。

Picture 2: Two test cases