喺二維平面上畀定 $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$ 顏色相同,所以唔合法。
喺第二個範例入面,存在合法嘅四邊形,但係無凸四邊形滿足要求。
喺第三個範例入面,無辦法組成任何合法嘅四邊形。
正如第四個範例所示,答案可能會非常大。