#P17935. Colorful Quadrilateral

Colorful Quadrilateral

Colorful Quadrilateral

平面上有 NN 个坐标互不相同的点。第 ii 个点坐标为 (xi,yi)(x_i,y_i),颜色为 cic_i。

你要选择颜色两两不同的四个点,并按某种顺序连接成一个四边形。允许内角恰好为 180∘180^\circ,但任意两条不相邻的边都不能有公共部分。

若能构造这样的四边形,设其最大面积为 SS,输出 2S2S;否则输出 00。四边形可以是凹四边形,不要求为凸四边形。

共有 TT 组测试数据。

输入格式

T
case_1
...
case_T

每组测试数据的格式为:

N
x_1 y_1 c_1
...
x_N y_N c_N

输出格式

每组测试数据输出一行,包含一个整数,表示最大面积的两倍;无法构造时输出 00。

数据范围

1≤T≤1041\le T\le10^4,4≤N≤1054\le N\le10^5,所有测试数据的 NN 之和不超过 10510^5。

∣xi∣,∣yi∣≤108|x_i|,|y_i|\le10^8,1≤ci≤N1\le c_i\le N。同一组中不同点的坐标不同。所有输入均为整数。

样例 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

输出:

15
17
0
20000000000000000