配点 : 100 点
問題文
N 有本笔直的棒。i 第几根棒的长度为 L_i 。
从这些棒中 3 选择一些棒,将它们作为 3 边(非退化)构成三角形。请判断是否存在这样的选棒方法,如果存在,请求出可以构成三角形的最大面积 2 的幂。
T 测试用例,因此请逐一回答。
制約
- 所有输入均为整数
- 1 \leq T \leq 2 \times 10^5
- 3 \leq N \leq 2 \times 10^5
- 2 \leq L_i \leq 20000
- L_i 是偶数
- 1 对于一个输入中包含的测试用例,N 的总和是 2 \times 10^5 以下
入力
输入是按以下格式从标准输入给出的。在这里, 这意味着第\mathrm{case}_i 是 您也可以写 i 个测试用例。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。 打印
N L_1 L_2 \dots L_N
出力
T 行。i 在线 i 个测试用例的答案。
每个测试用例中,如果不存在满足条件的选棒方法,则 -1 输出。如果存在满足条件的选棒方法,则输出可构成三角形的最大面积 2 输出所得到的值为整数。不过,在问题的约束下,可以证明该值将是整数。
入力例 1
3 5 2 2 2 2 2 7 2 6 4 10 8 10 20 5 4 16 36 64 100
出力例 1
3 1344 -1
2 个测试用例中, 通过操作3 边长为 8,10,10 的三角形是最大的,面积为 8\sqrt{21} 。在 2 功率为 1344 。
3 号测试用例中,无论组合哪 3 根棒,都无法形成三角形。