L - Largest Triangle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 本の棒を組み合わせても三角形を作ることはできません。