考场 d e b u f f debuff debuff太严重了 下来一眼沙比提
考虑其实就是 求一段区间 M a x ∣ ∑ i ∈ [ l , r ] ( x i , y i ) ∗ ( x , y ) ∣ Max|\sum_{i\in [l,r]}(x_i,y_i)*(x,y)| Max∣i∈[l,r]∑(xi,yi)∗(x,y)∣
因为叉积不同方向会有正负 由于有绝对值，可以拆成最大前缀和减去最小前缀和 先只考虑最大前缀和 即 M a x ∑ x i ∗ y − ∑ y i ∗ x Max \sum{x_i}*y-\sum{y_i}*x Max∑xi∗y−∑yi∗x 考虑2个前缀 i , j i,j i,j， i i i比 j j j大，则 ( ∑ x i − ∑ x j ) ∗ y − ( ∑ y i − ∑ y j ) ∗ x > 0 (\sum{x_i}-\sum{x_j})*y-(\sum{y_i}-\sum{y_j})*x>0 (∑xi−∑xj)∗y−(∑yi−∑yj)∗x>0 化一下就变成了 ( ∑ y i − ∑ y k ) ( ∑ x i − ∑ x j ) < y x \frac{(\sum{y_i}-\sum{y_k})}{(\sum{x_i}-\sum{x_j})}<\frac y x (∑xi−∑xj)(∑yi−∑yk)<xy
就是一个很裸地斜率式子了，每次二分即可 复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
#include<bits/stdc++.h> using namespace std; #define int long long const int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ob==ib)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } const int N=1000005; int X[N],Y[N],n,m1,m2,q; struct point{ int x,y; point(int _x=0,int _y=0):x(_x),y(_y){} friend inline point operator +(const point &a,const point &b){ return point(a.x+b.x,a.y+b.y); } friend inline point operator -(const point &a,const point &b){ return point(a.x-b.x,a.y-b.y); } friend inline int operator *(const point &a,const point &b){ return (a.x*b.y-a.y*b.x); } }p[N],up[N],down[N]; inline void graham(){ up[1]=down[1]=point(0,0),up[2]=down[2]=p[1],m1=m2=2; for(int i=2;i<=n;i++){ while(m1>=2&&(up[m1]-up[m1-1])*(p[i]-up[m1-1])>=0)m1--; up[++m1]=p[i]; while(m2>=2&&(p[i]-down[m2-1])*(down[m2]-down[m2-1])>=0)m2--; down[++m2]=p[i]; } } inline double calc(const point &a,double k){ return a.y-a.x*k; } inline double checkup(double k){ int l=1,res=l,r=m1; while(l<=r){ int mid=(l+r)>>1; if(calc(up[mid],k)>=calc(up[mid+1],k))r=mid-1,res=mid; else l=mid+1; } return calc(up[res],k); } inline double checkdown(double k){ int l=1,res=l,r=m2; while(l<=r){ int mid=(l+r)>>1; if(calc(down[mid],k)<=calc(down[mid+1],k))r=mid-1,res=mid; else l=mid+1; } return calc(down[res],k); } signed main(){ n=read(); for(int i=1;i<=n;i++)X[i]=read(),Y[i]=read(); for(int i=1;i<=n;i++)p[i]=p[i-1]+point(X[i],Y[i]); graham(); q=read(); for(int i=1;i<=q;i++){ int x=read(),y=read(); double k=1.0*y/x; double f1=checkup(k); double f2=checkdown(k); cout<<(int)round(x*(f1-f2))<<'\n'; } }