#P10630. [JOI Open 2017] 推土机

[JOI Open 2017] 推土机

题目描述

译自 JOI Open 2017 T2 「ブルドーザー / Bulldozer」

平面上有 NN 个点,点 i(1iN)i\:(1≤i≤N) 位于 (Xi,Yi)(X_i, Y_i),点 i(1iN)i\:(1≤i≤N) 的权值为非零整数 WiW_i(可能为负数)。
在平面上画两条平行线,所得的总价值为平行线之间(压线也算)所有点的权值之和。求总价值至多不超过多少。

输入格式

第一行包含一个整数 NN
在接下来的 NN 行中,第 ii 行包含三个用空格分隔的整数 Xi,Yi,WiX_i,Y_i,W_i

输出格式

一行,一个整数,表示最大总价值。

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7
19
6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2
15
5
0 0 2
4 0 2
3 2 -1
1 2 2
1 1 -1
5
2
0 0 -1
1 0 -1
0

提示

样例解释 1

选择点 2,3,4,52, 3, 4, 5

样例解释 2

注意,点 1,2,31,2,3 共线。点 4,5,64,5,6 共线。

样例解释 3

这组样例中没有三点共线。选择的平行线一条过点 1,21,2,另一条过点 3,43,4

数据范围

所有输入数据都满足以下条件。

1N2000,Xi,Yi109,1Wi109(1iN)1≤N≤2000, |X_i|,|Y_i|≤10^9,1 ≤|W_i|≤10^9(1≤i≤N)(Xi,Yi)(Xj,Yj)(1i<jN)(X_i,Y_i)≠(X_j,Y_j)\:(1≤i<j≤N)

子任务 分值 N100N≤100 无三点共线 LL 是在平面上通过两个不同点的一条线,LL' 是在平面上另一条通过两个不同点的线,那么 LLLL' 相互平行 其他条件
11 55 × 所有点都在 xx 轴上
22 2020
33 3535 ×
44 2020 ×
55 ×