102206: [AtCoder]ABC220 G - Isosceles Trapezium

Problem Statement

In the $xy$-plane, we have $N$ points, each assigned a weight.
The $i$-th point has the coordinates $(X_i,Y_i)$ and the weight $C_i$.

We will choose four of the $N$ points to form an isosceles trapezoid whose vertices are the chosen points.
What is the maximum possible total weight of the points chosen here?

If it is impossible to form an isosceles trapezoid, print -1.

We remind you that an isosceles trapezoid is a quadrilateral that satisfies all of the following conditions.

• It is a trapezoid.
• For one of the two parallel sides, the two angles at its ends are equal.

Constraints

• $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$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

40

We can choose Points $1, 2, 3, 5$ to form an isosceles trapezoid, with the points having a total weight of $40$.
Any other way to choose points would not form an isosceles trapezoid.

Sample Input 2

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

Sample Output 2

650021

Note that a square and a rectangle are also isosceles trapezoids.

Sample Input 3

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

Sample Output 3

-1

We cannot form an isosceles trapezoid.

问题描述

在$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$
• 如果$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$

输出

输出答案。

样例输入 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

我们无法构成等腰梯形。