G - 等腰梯形

分值：600分

题目描述

在 $xy$-平面上给定 $N$ 个点，每个点都有一个权重。

第 $i$ 个点的坐标为 $(X_i,Y_i)$，权重为 $C_i$。

我们要选择其中四个点来构成一个等腰梯形，选择的四个点的权重之和最大是多少？

如果无法构成等腰梯形，则输出 -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)$。
• 输入数据的所有值都是整数。

输入

从标准输入中读取输入数据，格式如下：

$N$

$X_1$ $Y_1$ $C_1$

$X_2$ $Y_2$ $C_2$

$\vdots$

$X_N$ $Y_N$ $C_N$

输出

输出答案。

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

40

我们可以选择 1、2、3、5 号点来形成一个等腰梯形，这四个点的权重之和为 40。
其他选择方式都无法构成等腰梯形。

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

650021

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

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

-1

我们无法构成等腰梯形。