AT_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 翻译