← 返回题目列表

AtCoder · abc220_g

G. 等腰梯形

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

分数: 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

我们无法形成等腰梯形。