设：
sw[i]为1..i的w之和
sd[i]为1到i的距离
cost[i]为把第一个锯木厂建在i带来的花费
all[i,j]为把i..j所有木头运到j所需要的花费
所以$all[i,j]=cost[j]-cost[i-1]-sw[i-1]*(sd[j]-sd[i-1])$
我们设第2个锯木厂建在i所带来的最小花费为f[i]，则$f[i]=min\{cost[j]+all[j+1,i]+all[j+1,n+1]\}$
把all化掉，最终变成$f[i]=min\{cost[n+1]-sw[j]*(sd[i]-sd[j])-sw[i]*(sd[n+1]-sd[i])\}$
这样的话，如果直接做，复杂度是$O(n^2)$的
考虑优化，我们尝试比较在i固定时，f[j1]和f[j2]的值（j1<j2）,$f[j1]-f[j2]=sw[j2]*(sd[i]-sd[j2])-sw[j1]*(sd[i]-sd[j1])$
先假设$f[j1]-f[j2]<0$，也就是j1是较优解
那么可以得到$\frac{sw[j1]*sd[j1]-sw[j2]*sd[j2]}{sw[j1]-sw[j2]}>sd[i]$
发现右端随i单增，而且左端呈现斜率的形式
那么也就是说，如果在某次i++以后，某两个j1,j2的斜率<sd[i]，就可以确定j1永远不会是最优解了
那么可以维护一个队列，保证j1<j2<j3<... ，而且j1j2 ,j2j3 ,j3j4两两间的斜率递增
这样在每次i++的时候，先从队头向后把斜率<sd[i]的踢掉，之后的队头就是这次i的最优值
然后在统计完i的答案以后，i也可以作为第一个伐木厂了，就把它按照性质从队尾插进去
也就是说，对于队尾的两个元素t-1和t，若t.i间斜率>t-1.t间斜率，直接把i插到队尾；
若不是，则踢掉t然后继续做（此时的t绝对不会是最优解了，因为t-1与i间斜率<t-1与t间斜率，则要么t-1比t和i都优，要么sd[i]先超过t-1与i间的斜率，然后i会优于t-1和t）
队列里只剩一个点的话就谈不来斜率了..就不做了...
然后做的时候可以把比较斜率的除法改成乘法，防止出锅
每个点最多进队一次，出队一次，所以复杂度是O(n)的
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<ctime>
#define LL long long int
using namespace std;
const int maxn=; LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,w[maxn],d[maxn];
LL sw[maxn],sd[maxn],cost;
int q[maxn],head,tail; inline bool judge1(int j1,int j2,int i){return sw[j1]*sd[j1]-sw[j2]*sd[j2]<sd[i]*(sw[j1]-sw[j2]);}
inline bool judge2(int j1,int j2,int j3){return (sw[j1]*sd[j1]-sw[j2]*sd[j2])*(sw[j2]-sw[j3])<(sw[j2]*sd[j2]-sw[j3]*sd[j3])*(sw[j1]-sw[j2]);}
inline int get(int i,int j){return cost-sw[j]*(sd[i]-sd[j])-sw[i]*(sd[N+]-sd[i]);} int main(){
int i,j,k;
N=rd();
for(i=;i<=N;i++){
w[i]=rd(),d[i]=rd();
sw[i]=sw[i-]+w[i];sd[i]=sd[i-]+d[i-];
cost+=sw[i-]*d[i-];
}cost+=sw[N]*d[N];sd[N+]=sd[N]+d[N];
head=tail=;q[]=;
int ans=2e9+;
for(i=;i<=N;i++){
while(head<tail&&(!judge1(q[head],q[head+],i))) head++;
ans=min(ans,get(i,q[head]));
while(tail>head&&(!judge2(q[tail-],q[tail],i))) tail--;
q[++tail]=i;
}printf("%d\n",ans); return ;
}