G - Isosceles Trapezium Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

xy 平面上に N 個の点があり、それぞれの点に重みがついています。
i 個目の点の座標は (X_i,Y_i) で、重みは C_i です。

N 点の中から 4 点を選んで、それらを頂点とする面積が正の等脚台形を作ります。
このとき、選んだ 4 点の重みの和の最大値はいくつですか？

等脚台形を作ることができないときは -1 と出力してください。

なお、等脚台形とは以下の条件を全て満たす四角形のことです。

  • 台形である
  • 平行な 2 つの辺のうち、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

等脚台形を作ることはできません。

Score : 600 points

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.