int n,cnt,f[MAX];
pii a[MAX],d[MAX];
signed q[MAX],head,tail;
#define X(i) (d[i+1].fi)
#define Y(i) ((-f[i]))
inline void mian()
{
read(n);
for(int i=1;i<=n;++i) read(a[i].fi,a[i].se);
sort(a+1,a+n+1,[&](pii x,pii y){return x.fi==y.fi?x.se>y.se:x.fi>y.fi;});
for(int i=1;i<=n;++i) if(d[cnt].se<a[i].se) d[++cnt]=a[i];
q[1]=0,head=1,tail=1;
for(int i=1;i<=cnt;++i)
{
while(head<tail&&1.0*(Y(q[head+1])-Y(q[head]))/(X(q[head+1])-X(q[head]))<=d[i].se) ++head;
f[i]=f[q[head]]+d[q[head]+1].fi*d[i].se;
while(head<tail&&(Y(q[tail])-Y(q[tail-1]))*(X(i)-X(q[tail]))>=(Y(i)-Y(q[tail]))*(X(q[tail])-X(q[tail-1]))) --tail;
q[++tail]=i;
}
write(f[cnt],'\n');
}
下面这段代码可以通过本题,但是将第 16 行的
while(head<tail&&1.0*(Y(q[head+1])-Y(q[head]))/(X(q[head+1])-X(q[head]))<=d[i].se) ++head;
替换成
while(head<tail&&Y(q[head+1])-Y(q[head])<=d[i].se*(X(q[head+1])-X(q[head]))) ++head;
就会出现队首无法弹出的问题,这是为什么呢?