AT_1_stpc2025_1_l.Colorful Quadrilateral

在二维平面上有 $N$ 个不同的点，每个点编号为 $1$ 到 $N$。第 $i$ 个点的坐标是 $(x_i, y_i)$。

此外，每个点都有一种颜色。颜色的种类共有 $N$ 种，也按 $1$ 到 $N$ 编号。第 $i$ 个点的颜色是 $c_i$。

你可以从这些点中选择颜色各不相同的 $4$ 个点，以任意顺序连接，构成一个四边形。这个四边形可以包含恰好 $180^\circ$ 的内角，但任意两条不连续的边不能有公共部分（即不相交）。

请判断是否能构成这样的四边形。如果可以，求四边形可能的最大面积 $S$，并输出 $2S$。如果无法构成，输出 $0$。

有 $T$ 组测试数据，需要分别求解。

输入按以下格式给出。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例，格式如下：

$N$ $x_1$ $y_1$ $c_1$ $x_2$ $y_2$ $c_2$ $\vdots$ $x_N$ $y_N$ $c_N$

请针对 $T$ 个测试用例，按行输出答案。

样例解释 1

对于第 1 个测试点，选取点 $1,2,3,6$ 按这个顺序连接可以构成一个符合条件的四边形，其面积为 $15/2$。这个四边形是在所有符合条件的四边形中面积最大的。选择点 $1,2,4,5$ 连接得到的面积为 $9$，但 $1$ 和 $4$ 的颜色相同，因此不符合要求。

第 2 个测试点可以构成符合条件的四边形，但无法构成凸四边形。

第 3 个测试点无法构成符合条件的四边形。

第 4 个测试点可能会出现非常大的答案。

数据范围

• 所有输入均为整数。
• $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$。

由 ChatGPT 5 翻译