分数: 600 点
问题陈述
在 xy- 飞机,我们有 N 点,每个点分配一个权重。
的 i第一个点有坐标 (X_i,Y_i) 和重量 C_i.
我们将选择其中的四个 N 点形成一个等腰梯形,其顶点是所选点。
此处选择的点的最大可能总权重是多少?
如果无法形成等腰梯形,则打印 -1.
我们提醒您,等腰梯形是满足以下所有条件的四边形。
- 这是一个梯形。
- 对于两条平行边之一,其两端的两个角度相等。
约束
- 4 \leq N \leq 1000
- -10^9 \leq X_i,Y_i \leq 10^9
- 1 \leq C_i \leq 10^9
- (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 C_1 X_2 Y_2 C_2 \vdots X_N Y_N C_N
输出
打印答案。
示例输入 1
5 0 3 10 3 3 10 -1 0 10 2 0 10000 4 0 10
示例输出 1
40
我们可以选择积分 1, 2, 3, 5 形成一个等腰梯形,各点的总重量为 40.
任何其他选择点的方式都不会形成等腰梯形。
示例输入 2
6 0 1 1 1 4 20 2 7 300 5 6 4000 4 3 50000 3 0 600000
示例输出 2
650021
请注意,正方形和矩形也是等腰梯形。
示例输入 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
我们无法形成等腰梯形。