在二維平面上給定 $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$ 的顏色相同,因此不合法。
在第二個範例中,存在合法的四邊形,但沒有凸四邊形滿足要求。
在第三個範例中,無法形成任何合法的四邊形。
如第四個範例所示,答案可能會非常大。