#P17935. Colorful Quadrilateral
Colorful Quadrilateral
Colorful Quadrilateral
平面上有 个坐标互不相同的点。第 个点坐标为 ,颜色为 。
你要选择颜色两两不同的四个点,并按某种顺序连接成一个四边形。允许内角恰好为 ,但任意两条不相邻的边都不能有公共部分。
若能构造这样的四边形,设其最大面积为 ,输出 ;否则输出 。四边形可以是凹四边形,不要求为凸四边形。
共有 组测试数据。
输入格式
T
case_1
...
case_T
每组测试数据的格式为:
N
x_1 y_1 c_1
...
x_N y_N c_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