Universal Cup Judging System

Universal Cup

実行時間制限: 4.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

二次元平面上に $N$ 個の相異なる点が与えられ、$1$ から $N$ までの番号が付けられています。点 $i$ の座標は $(x_i, y_i)$ です。

各点には色が付いています。色は全部で $N$ 種類あり、$1$ から $N$ までの番号が付けられています。点 $i$ の色は $c_i$ です。

あなたの仕事は、色が互いに異なる四つの点を選び、それらを任意の順序で結んで四角形を作ることです。この四角形はちょうど $180^\circ$ の内角を持っても構いませんが、隣り合わない二辺が交差してはなりません。

このような四角形を作ることができるか判定してください。作ることができる場合、条件を満たす四角形の面積の最大値を $S$ として、$2S$ を整数として出力してください。作ることができない場合は $0$ を出力してください。

$T$ 個の独立なテストケースが与えられます。

入力

入力は以下の形式で与えられます:

T
case1
case2
:
caseT

ここで、各 $\text{case}_i$ は以下の形式で与えられます:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • 入力される値はすべて整数である。
  • $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)$ である。
  • すべてのテストケースにおける $N$ の総和は $10^5$ を超えない。

出力

各テストケースについて、答えをそれぞれ一行に出力してください。

入出力例

入力例 1

4
6
2 4 1
5 4 2
6 2 3
5 1 1
2 1 2
1 3 4
4
1 1 1
3 5 2
7 2 3
4 3 4
5
0 0 1
0 1 2
1 0 2
0 2 3
2 0 3
4
0 0 1
0 100000000 2
100000000 0 3
100000000 100000000 4

出力例 1

15
17
0
20000000000000000

ノート

最初の例では、点 $1, 2, 3, 6$ をこの順に結ぶと面積 $15/2$ の有効な四角形が得られ、これはすべての有効な選び方の中で最大です。点 $1, 2, 4, 5$ からなる四角形の面積は $9$ ですが、点 $1$ と点 $4$ の色が同じであるため無効です。

二番目の例では、有効な四角形は存在しますが、条件を満たす凸四角形は存在しません。

三番目の例では、有効な四角形を作ることはできません。

四番目の例に示されている通り、答えは非常に大きくなることがあります。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.