AT_stpc2025_1_l Colorful Quadrilateral

$ 2 $ 次元平面上に相異なる $ N $ 個の点があり、それぞれ $ 1 $ から $ N $ までの番号が付けられています。点 $ i $ の座標は $ (x_i, y_i) $ です。 また、それぞれの点には色が付けられています。色の種類は $ N $ 個あり、それぞれ $ 1 $ から $ N $ までの番号が付けられています。点 $ i $ の色は $ c_i $ です。 あなたは、これらの点から色の相異なる $ 4 $ 点を選び、任意の順でつないで $ 1 $ つの四角形を作ります。この四角形はちょうど $ 180 $ 度の内角を持っていても構いませんが、連続しないどの $ 2 $ 辺も共通部分を持ってはいけません。 そのように四角形を作ることができるかどうか判定し、できる場合はその四角形の面積としてあり得る最大値を $ S $ として $ 2S $ を出力してください。できない場合は $ 0 $ を出力してください。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ ここで、 $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表し、次の形式で与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ $ \vdots $ $ x_N $ $ y_N $ $ c_N $

$ T $ 個のテストケースについて答えを改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースでは、点 $ 1,2,3,6 $ をこの順でつないでできる四角形は条件を満たしており、その面積は $ 15/2 $ です。この四角形は条件を満たす四角形のうち面積が最大です。点 $ 1,2,4,5 $ をこの順でつないでできる四角形の面積は $ 9 $ ですが、点 $ 1,4 $ の色は同じなので、この四角形は条件を満たしていません。 $ 2 $ 番目のテストケースでは、条件を満たす四角形を作ることができますが、凸であるものを作ることはできません。 $ 3 $ 番目のテストケースでは、条件を満たす四角形を作ることはできません。 $ 4 $ 番目のテストケースのように、答えが非常に大きくなる場合があることに注意してください。 ### Constraints - 入力はすべて整数 - $ 1\le T\le 10^4 $ - $ 4\le N\le 10^5 $ - $ |x_i|,|y_i|\le 10^8 $ - $ 1\le c_i\le N $ - $ i\neq j $ ならば $ (x_i,y_i)\neq (x_j,y_j) $ - $ T $ 個のテストケースに渡る $ N $ の総和は $ 10^5 $ 以下