← 返回题目列表

AtCoder · utpc2023_l

L. 最大的三角形

中文机器翻译题面 查看原题

配点 : 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 根棒,都无法形成三角形。