#P17878. Harmonizing Charges

Harmonizing Charges

题目描述

数轴上有 nn 个点电荷,编号为 1,2,…,n1,2,\ldots,n,位置两两不同。第 ii 个点电荷的电荷量为 qiq_i,坐标为 xix_i。本题定义两个不同点电荷 i,ji,j 之间的作用力大小为

qiqj(xi−xj)2.\frac{q_iq_j}{(x_i-x_j)^2}.

你需要把所有点电荷划分到两个非空集合 A,BA,B 中。部分点电荷可能已经指定了所属集合,这些归属不能更改。

请为尚未分配的点电荷选择集合,使得所有属于同一集合的不同点电荷对之间的作用力的最小值尽可能大。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例的第一行包含整数 nn。

接下来 nn 行,第 ii 行包含两个整数 qi,xiq_i,x_i 和一个字符 sis_i:

  • A 表示已经分配到集合 AA;
  • B 表示已经分配到集合 BB;
  • ? 表示尚未分配。

输出格式

对每个测试用例输出一行,表示最小作用力的最大可能值。

答案必须表示为正整数分子、分母构成的最简分数,格式为 p/q。

样例

2
5
3 6 ?
2 4 ?
3 1 ?
5 7 ?
4 2 ?
4
1 1 A
2 2 B
3 3 ?
4 4 B
10/9
2/1

数据范围

  • 1≤T≤10001\le T\le1000;
  • 4≤n≤1054\le n\le10^5;
  • 1≤qi≤150001\le q_i\le15000,1≤xi≤2×1051\le x_i\le2\times10^5;
  • 每个测试用例内坐标两两不同,且至少有一个点电荷尚未分配;
  • 每个输入文件中所有测试用例的 nn 之和不超过 5×1055\times10^5。