#P17940. Hoshizora

Hoshizora

Hoshizora

平面上有 nn 个物体,每个物体沿一条固定直线做匀速运动,也可以静止。两张照片记录了物体在两个不同时刻的位置:第 ii 个物体的位置分别为 (x1,i,y1,i)(x_{1,i},y_{1,i}) 和 (x2,i,y2,i)(x_{2,i},y_{2,i})。

可以把两次拍照时刻分别设为 00 和 11。在任意实数时刻 tt,第 ii 个物体位于

$$P_i(t)=(x_{1,i},y_{1,i})+t(x_{2,i}-x_{1,i},y_{2,i}-y_{1,i}).$$

输入还给出每个物体质量的倒数 mi′m'_i。对每个 ii,求

$$\min_{j\ne i}\ \min_{t\in\mathbb R} m'_i m'_j\,\|P_i(t)-P_j(t)\|^2.$$

时间可以为负数,也可以在两次拍照之后;并不限于 [0,1][0,1]。物体的轨迹不会因引力改变。这个量相当于任意另一物体所产生的最大引力除以引力常数后再取倒数。

输入格式

第一行是测试用例数 tt,1≤t≤1041\le t\le10^4。

每组用例第一行包含整数 nn;第二行包含 nn 个整数 m1′,…,mn′m'_1,\ldots,m'_n。接下来 nn 行,每行四个整数 x1,i,y1,i,x2,i,y2,ix_{1,i},y_{1,i},x_{2,i},y_{2,i}。

  • 2≤n2\le n,所有用例的 ∑n≤105\sum n\le10^5;
  • 1≤mi′≤1001\le m'_i\le100;
  • 所有坐标在 [−108,108][-10^8,10^8] 内;
  • ∣x1,i−x2,i∣≤5|x_{1,i}-x_{2,i}|\le5,∣y1,i−y2,i∣≤5|y_{1,i}-y_{2,i}|\le5。

输出格式

每组用例输出一行 nn 个实数,依次表示各物体的答案。

设输出值为 xx,标准答案为 yy。当且仅当

∣x−y∣max⁡(y,1)≤10−6\frac{|x-y|}{\max(y,1)}\le10^{-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
2.000000000 2.000000000
3.000000000 4.000000000 3.000000000