AT_abc448_g [ABC448G] Conquest

高桥和青木进行一场牌组游戏。游戏规则如下。 - 高桥准备牌组 $A_1, A_2, \dots, A_N$，其中 $N \geq 3$。 - 青木准备牌组 $B_1, B_2, B_3$。 - 高桥从青木的牌组中选择一组并将其封禁。青木也从高桥的牌组中选择一组并将其封禁。两人封禁操作**同时**进行（即任何一方无法根据对方的选择行动）。 - 然后，高桥和青木各自**同时**声明将使用自己的哪一组牌组，但已被封禁的牌组不能被声明。 - 接下来，两位玩家各用宣布的牌组战斗一次。本局会有一方获胜。 给定整数 $X_{i,j}$（$1 \leq i \leq N, 1 \leq j \leq 3$）。记 $p_{i,j} = \dfrac{X_{i,j}}{10^6}$。$p_{i,j}$ 表示高桥使用 $A_i$ 与青木使用 $B_j$ 时高桥的胜率。两人都预先知道 $p_{i,j}$ 的值。 请计算当双方都采取使自己胜率最大化的行动时，高桥的胜率。 共给出 $T$ 组测试数据，请分别求解。 当双方都想最大化自己的胜率时，每一步每位玩家会为可选项分配概率（概率总和为 $1$），并根据到目前为止公开的信息按概率随机选择一个选项。 每位玩家会选择使“最小可能胜率”最大的策略，即“当对方选择使自己胜率最小的策略时的胜率”。如果有多个满足条件的策略，可以任选其一。 当双方均按上述方针行动时，无论具体策略如何，高桥的胜率均唯一确定。请输出该值。

输入从标准输入读入，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试数据。 > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据包含： > $N$ > $X_{1,1}\ X_{1,2}\ X_{1,3}$ > $X_{2,1}\ X_{2,2}\ X_{2,3}$ > $\vdots$ > $X_{N,1}\ X_{N,2}\ X_{N,3}$

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试数据的答案。 对于每组测试数据，当双方都采取最大化自己胜率的策略时，高桥的胜率是多少。若输出的答案与真实值的绝对误差或相对误差不超过 $10^{-6}$，即视为正确。

### 样例解释 1 双方都最大化自己胜率时，高桥的胜率为 $0.5272727\cdots$。 ### 约束条件 - $1 \leq T \leq 500$ - $3 \leq N \leq 5 \times 10^4$ - $0 \leq X_{i,j} \leq 10^6$ - 所有测试数据中 $N$ 之和不超过 $5 \times 10^4$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译