平面上有 $N$ 个点，点 $i$ 位于 $(X_i, Y_i)$，权值为非零整数 $W_i$（可能为负数）。

在平面上画两条平行线，所得的总价值为平行线之间（压线也算）所有点的权值之和。求总价值的最大值。

$N\le 2000, |X_i|,|Y_i|,|W_i|\le 10^9,(X_i,Y_i)≠(X_j,Y_j)\:(i\neq j)$ 。

先考虑平行线的斜率，初步猜测为是两点间的斜率。

但是稍加观察我们发现应该是两点间斜率 $\pm\,\varepsilon$​​​ 比较准确，因为可能有若干点共线的情况。

$\pm\,\varepsilon$ 这个形式太丑了，我们尝试优美点描述：

设两点间斜率从小到大依次为：$k_1,k_2,\cdots,k_m$。我们依次考虑斜率在 $(-\infty,k_1),[k_1,k_2),\cdots,[k_{m-1},k_m),[k_m,\infty)$ 的时候的答案。

显然在题目条件下，这整个区间都是等价的。

然后我们尝试描述被两条平行线夹在中间的点。

考虑和平行线垂直的任意一条直线，然后考虑所有点在这条线上的投影（垂直和投影的垂直，应该懂为啥了吧），如下图：

于是我们发现相当于投影上的一个区间，并且显然是双射的。

或者说，把这条直线顺次做扫描，扫描到的点依次加入一个序列，这东西对应序列的区间。

然后维护出区间，就转换为最大子段和问题。

然后我们考虑斜率改变的时候，序列会怎么改变。

初始由于斜率 $-\infty$，序列就是按照 $(x,y)$ 坐标这个二元组排序的结果。

一样的，只有在两个点连线的斜率被扫描后，这两点在序列中的位置才会交换。

直接扫描，线段树维护最大子段和，复杂度 $O(N^2\log N)$​。

注意按斜率排序的时候，如果斜率相等，pair $(i,j)$ 小的要在前面，其中 $(i,j)$ 是形成此斜率的两点。

我把这归类为平几维护相对顺序的问题。类似题目 P4864，还有 nfls《直线交点》。

上面两题说的事情是：按 $x$ 坐标做扫描线，维护直线在 $x=X$ 时的相对顺序（例如求 $\texttt{kth}$​）。

可以把直线看成序列中的元素，初始按照斜率排序（$x=-\infty$ 的值）。

然后每扫到一个交点，交换对应两条线在序列中的位置，就维护了相对顺序。

交换次数为 $O(n^2)$​。

• 这题其实不太一样，是把点投影到直线上，要维护点的相对顺序。

//洛谷 P10630
//https://www.luogu.com.cn/problem/P10630
#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,LL>
#define x first
#define y second
#define ls w<<1
#define rs w<<1|1
#define lw l,m,ls
#define rw m+1,r,rs
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2005;
int n,m,p[N];LL ans;
struct E{P t;LL w;}A[N];
struct F{P t,id;}B[N*N/2];
inline LL operator*(P A,P B){return A.x*B.y-A.y*B.x;}
struct T{LL sl,sr,s,mx;}a[N<<2];
inline void ins(T &A,int t){A={t,t,t,t};}
inline void pu(int w)
{
	a[w].sl=max(a[ls].s+a[rs].sl,a[ls].sl);
	a[w].sr=max(a[rs].s+a[ls].sr,a[rs].sr);
	a[w].s=a[ls].s+a[rs].s;
	a[w].mx=max({a[ls].mx,a[rs].mx,a[ls].sr+a[rs].sl});
}
void bd(int l=1,int r=n,int w=1)
{
	if(l==r) return ins(a[w],A[l].w);
	int m=(l+r)>>1;bd(lw),bd(rw),pu(w);
}
void upd(int p,LL t,int l=1,int r=n,int w=1)
{
	if(l==r) return ins(a[w],t);int m=(l+r)>>1;
	p<=m?upd(p,t,lw):upd(p,t,rw);pu(w);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
	for(int i=1;i<=n;i++) cin>>A[i].t.x>>A[i].t.y>>A[i].w,p[i]=i;
	sort(A+1,A+1+n,[](E A,E B){return A.t<B.t;});bd();
	for(int i=1;i<=n;i++) for(int j=1;j<i;j++)
		B[++m]={{A[i].t.x-A[j].t.x,A[i].t.y-A[j].t.y},{i,j}};
	sort(B+1,B+1+m,[](F A,F B){
		LL t=A.t*B.t;return !t?A.id<B.id:t<0;
	});
	ans=max(0ll,a[1].mx);
	for(int i=1,j;i<=m;i=j)
	{
		for(j=i+1;j<=m&&!(B[i].t*B[j].t);j++);
		for(int k=i;k<j;k++)
		{
			auto [u,v]=B[k].id;
			upd(p[u],A[v].w),upd(p[v],A[u].w),swap(p[u],p[v]);
		}ans=max(ans,a[1].mx);
	}
	return cout<<ans,0;
}