Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

在二維平面上給定 $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.