← 返回题目列表

AtCoder · stpc2025_1_l

L. 彩色四边形

中文机器翻译题面 查看原题

配点 : 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 请注意,在第个测试用例中,答案可能会非常大。