AT_abc220_g [ABC220G] Isosceles Trapezium

题目描述

在 $xy$ 平面上有 $N$ 个点，每个点都有一个权值。
第 $i$ 个点的坐标为 $(X_i, Y_i)$，权值为 $C_i$。

请从 $N$ 个点中选出 $4$ 个点，使得它们作为顶点能够构成一个面积为正的等腰梯形。
在这种情况下，所选 $4$ 个点的权值和的最大值是多少？

如果无法构成等腰梯形，请输出 $-1$。

等腰梯形需满足以下所有条件：

• 是梯形；
• 在两条平行边中，其中一条边的两个端点的角相等。

输入格式

输入以如下格式从标准输入给出。

$N$
$X_1\ Y_1\ C_1$
$X_2\ Y_2\ C_2$
$\vdots$
$X_N\ Y_N\ C_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5
0 3 10
3 3 10
-1 0 10
2 0 10000
4 0 10

输出 #1

40

输入输出样例 #2

输入 #2

6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

输出 #2

650021

输入输出样例 #3

输入 #3

7
-3 0 1
-2 0 1
-1 0 1
0 0 1
1 0 1
2 0 1
3 0 1

输出 #3

-1

说明/提示

限制条件

• $4 \leq N \leq 1000$
• $-10^9 \leq X_i, Y_i \leq 10^9$
• $1 \leq C_i \leq 10^9$
• 若 $i \neq j$，则 $(X_i, Y_i) \neq (X_j, Y_j)$
• 所有输入均为整数

样例解释 1

选择点 $1,2,3,5$ 可以构成等腰梯形，点的权值和为 $40$。除此之外，没有其他选法可以构成等腰梯形。

样例解释 2

请注意，正方形和长方形也属于等腰梯形。

样例解释 3

无法构成等腰梯形。

由 ChatGPT 4.1 翻译