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.