配点 : 100 点
問題文
2 在二维平面上,互不相同的 N 点,每个点都有 它们的编号最大为 1 减去 N 点被标有从 到 的编号。 i 的坐标为 (x_i, y_i) 。
此外,每个点都被赋予了一种颜色。颜色的种类有 N 种,分别为 1 减去 N 点被标有从 到 的编号。 i 的颜色是 c_i 。
你需要从这些点中选择颜色各不相同的 4 个点,并按任意顺序连接它们 1 个点组成一个四边形。这个四边形允许恰好具有 180 度的内角,但任意两条不相邻的 2 边都不能有公共部分。
请判断是否能够构造出这样的四边形,如果可以,输出该四边形面积可能达到的最大值 S 作为 2S 。如果不能,请输出 0 请输出。
T 测试用例,因此请解决每个测试用例。
制約
- 所有输入均为整数
- 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)
- T 个测试用例中的 N 总和为 10^5 以下
入力
输入按以下格式给出。
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
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 个测试用例输出答案,每个答案占一行。在第 1,2,3,6 个测试用例中,按此顺序连接点 15/2 得到的四边形满足条件,其面积为 1,2,4,5 。在满足条件的四边形中,该四边形的面积最大。按此顺序连接点 9 得到的四边形面积为 1,4 ,但由于点的颜色相同,该四边形不满足条件。
2 在第个测试用例中,可以构造满足条件的四边形,但无法构造凸四边形。
3 在第个测试用例中,无法构造满足条件的四边形。
4 请注意,在第个测试用例中,答案可能会非常大。