3 条题解

  • 1
    @ 2023-10-10 13:22:41

    #include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; const int maxn=5E5+5; const int base=33333; const ld eps=1E-10; const ld inf=1E17; int n,m,T; ll a[maxn],b[maxn],ans[maxn]; int idR[maxn],idL[maxn]; ld rightPlane[maxn],leftPlane[maxn]; int q[maxn]; struct pt { double x,y; pt(double a=0,double b=0):x(a),y(b){} pt operator+(const pt&A){return pt(x+A.x,y+A.y);} pt operator-(const pt&A){return pt(x-A.x,y-A.y);} pt operator*(ld d){return pt(xd,yd);} double operator*(const pt&A){return xA.y-yA.x;} void out(){cout<<"("<<x<<","<<y<<")"<<endl;} }; struct line { pt A,B; int id,b; int slope; line(){} line(pt a,pt b):A(a),B(b){} }s[maxn]; inline ll max(ll x,ll y) { return x>y?x:y; } inline ll min(ll x,ll y) { return x<y?x:y; } inline ll get(ll x,ll a,ll b) { return (ax+b)x; } inline int read() { bool flag=0; char ch=getchar(); if(ch=='-') flag^=1; while(!isdigit(ch)) { ch=getchar(); if(ch=='-') flag^=1; } int sum=ch-'0'; ch=getchar(); while(isdigit(ch)) { sum=sum10+ch-'0'; ch=getchar(); } return flag?-sum:sum; } void write(ll x) { if(x>=10) write(x/10); putchar('0'+x%10); } inline void writen(ll x) { if(x<0) { putchar('-'); write(-x); } else write(x); putchar('\n'); } inline int cross(pt A,pt B) { ld d=AB; if(abs(d)<=eps) return 0; return d>0?1:-1; } inline pt intersection(line a,line b) { pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A; if(cross(A,B)0) return pt(inf,inf); ld d=-(BC)/(BA); return b.A+A*d; } inline int onClockwise(line a,line b,line c) { return cross(a.B-a.A,intersection(b,c)-a.A)-1; } bool cmpR(line A,line B) { if(A.slopeB.slope) return A.b<B.b; return A.slope<B.slope; } bool cmpL(line A,line B) { if(A.slopeB.slope) return A.b>B.b; return A.slope<B.slope; } void initR() { sort(s+1,s+n+1,cmpR); int L=1,R=0; for(int i=1;i<=n;++i) { while(i!=n&&s[i].slopes[i+1].slope) ++i; while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]])) --R; q[++R]=i; } for(int i=1;i<=R;++i) idR[i]=s[q[i]].id; for(int i=1;i<R;++i) rightPlane[i]=intersection(s[q[i]],s[q[i+1]]).x; int pos=1; for(int i=-base;i<=base;++i) { while(pos<R&&rightPlane[pos]<ld(i)) ++pos; ans[i+base]=get(i,s[q[pos]].slope,s[q[pos]].b); } } void initL() { sort(s+1,s+n+1,cmpL); int L=1,R=0; for(int i=1;i<=n;++i) { while(i!=n&&s[i].slopes[i+1].slope) ++i; while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]])) --R; q[++R]=i; } for(int i=1;i<=R;++i) idL[i]=s[q[i]].id; for(int i=1;i<R;++i) leftPlane[i]=intersection(s[q[i]],s[q[i+1]]).x; int pos=1; for(int i=base;i>=-base;--i) { while(pos<R&&ld(i)<leftPlane[pos]) ++pos; ans[i+base]=max(ans[i+base],get(i,s[q[pos]].slope,s[q[pos]].b)); } } int main() { // freopen("A.in","r",stdin); // freopen("A.out","w",stdout); ios::sync_with_stdio(false); n=read(),T=read(); for(int i=1;i<=n;++i) { a[i]=read(),b[i]=read(); s[i].A=pt(0,b[i]); s[i].B=pt(1,a[i]+b[i]); s[i].slope=a[i]; s[i].b=b[i]; s[i].id=i; } initR(); for(int i=1;i<=n;++i) swap(s[i].A,s[i].B); initL(); while(T--) { int x=read(); writen(ans[x+base]); } return 0; }

    • 1
      @ 2023-3-25 17:46:09
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long int ll;
      typedef long double ld;
      const int maxn=5E5+5;
      const int base=33333;
      const ld eps=1E-10;
      const ld inf=1E17;
      int n,m,T;
      ll a[maxn],b[maxn],ans[maxn];
      int idR[maxn],idL[maxn];
      ld rightPlane[maxn],leftPlane[maxn];
      int q[maxn];
      struct pt
      {
      double x,y;
      pt(double a=0,double b=0):x(a),y(b){}
      pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
      pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
      pt operator*(ld d){return pt(x*d,y*d);}
      double operator*(const pt&A){return x*A.y-y*A.x;}
      void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
      };
      struct line
      {
      pt A,B;
      int id,b;
      int slope;
      line(){}
      line(pt a,pt b):A(a),B(b){}
      }s[maxn];
      inline ll max(ll x,ll y)
      {
      return x>y?x:y;
      }
      inline ll min(ll x,ll y)
      {
      return x<y?x:y;
      }
      inline ll get(ll x,ll a,ll b)
      {
      return (a*x+b)*x;
      }
      inline int read()
      {
      bool flag=0;
      char ch=getchar();
      if(ch=='-')
      flag^=1;
      while(!isdigit(ch))
      {
      ch=getchar();
      if(ch=='-')
      flag^=1;
      }
      int sum=ch-'0';
      ch=getchar();
      while(isdigit(ch))
      {
      sum=sum*10+ch-'0';
      ch=getchar();
      }
      return flag?-sum:sum;
      }
      void write(ll x)
      {
      if(x>=10)
      write(x/10);
      putchar('0'+x%10);
      }
      inline void writen(ll x)
      {
      if(x<0)
      {
      putchar('-');
      write(-x);
      }
      else
      write(x);
      putchar('\n');
      }
      inline int cross(pt A,pt B)
      {
      ld d=A*B;
      if(abs(d)<=eps)
      return 0;
      return d>0?1:-1;
      }
      inline pt intersection(line a,line b)
      {
      pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
      if(cross(A,B)==0)
      return pt(inf,inf);
      ld d=-(B*C)/(B*A);
      return b.A+A*d;
      }
      inline int onClockwise(line a,line b,line c)
      {
      return cross(a.B-a.A,intersection(b,c)-a.A)==-1;
      }
      bool cmpR(line A,line B)
      {
      if(A.slope==B.slope)
      return A.b<B.b;
      return A.slope<B.slope;
      }
      bool cmpL(line A,line B)
      {
      if(A.slope==B.slope)
      return A.b>B.b;
      return A.slope<B.slope;
      }
      void initR()
      {
      sort(s+1,s+n+1,cmpR);
      int L=1,R=0;
      for(int i=1;i<=n;++i)
      {
      while(i!=n&&s[i].slope==s[i+1].slope)
      ++i;
      while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
      --R;
      q[++R]=i;
      }
      for(int i=1;i<=R;++i)
      idR[i]=s[q[i]].id;
      for(int i=1;i<R;++i)
      rightPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
      int pos=1;
      for(int i=-base;i<=base;++i)
      {
      while(pos<R&&rightPlane[pos]<ld(i))
      ++pos;
      ans[i+base]=get(i,s[q[pos]].slope,s[q[pos]].b);
      }
      }
      void initL()
      {
      sort(s+1,s+n+1,cmpL);
      int L=1,R=0;
      for(int i=1;i<=n;++i)
      {
      while(i!=n&&s[i].slope==s[i+1].slope)
      ++i;
      while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
      --R;
      q[++R]=i;
      }
      for(int i=1;i<=R;++i)
      idL[i]=s[q[i]].id;
      for(int i=1;i<R;++i)
      leftPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
      int pos=1;
      for(int i=base;i>=-base;--i)
      {
      while(pos<R&&ld(i)<leftPlane[pos])
      ++pos;
      ans[i+base]=max(ans[i+base],get(i,s[q[pos]].slope,s[q[pos]].b));
      }
      }
      int main()
      {
      //    freopen("A.in","r",stdin);
      //    freopen("A.out","w",stdout);
      ios::sync_with_stdio(false);
      n=read(),T=read();
      for(int i=1;i<=n;++i)
      {
      a[i]=read(),b[i]=read();
      s[i].A=pt(0,b[i]);
      s[i].B=pt(1,a[i]+b[i]);
      s[i].slope=a[i];
      s[i].b=b[i];
      s[i].id=i;
      }
      initR();
      for(int i=1;i<=n;++i)
      swap(s[i].A,s[i].B);
      initL();
      while(T--)
      {
      int x=read();
      writen(ans[x+base]);
      }
      return 0;
      }
      
      
      • 1
        @ 2022-5-24 16:10:54

        首先将xx大于00还是小于00分类,对于某一类全都除以xx,那么就得到了一些直线。最优的答案一定在某条最上方或最下方的直线上,半平面交或凸包维护即可。

        #include<bits/stdc++.h>
        using namespace std;
        typedef long long int ll;
        typedef long double ld;
        const int maxn=5E5+5;
        const int base=33333;
        const ld eps=1E-10;
        const ld inf=1E17;
        int n,m,T;
        ll a[maxn],b[maxn],ans[maxn];
        int idR[maxn],idL[maxn];
        ld rightPlane[maxn],leftPlane[maxn];
        int q[maxn];
        struct pt
        {
        double x,y;
        pt(double a=0,double b=0):x(a),y(b){}
        pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
        pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
        pt operator*(ld d){return pt(x*d,y*d);}
        double operator*(const pt&A){return x*A.y-y*A.x;}
        void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
        };
        struct line
        {
        pt A,B;
        int id,b;
        int slope;
        line(){}
        line(pt a,pt b):A(a),B(b){}
        }s[maxn];
        inline ll max(ll x,ll y)
        {
        return x>y?x:y;
        }
        inline ll min(ll x,ll y)
        {
        return x<y?x:y;
        }
        inline ll get(ll x,ll a,ll b)
        {
        return (a*x+b)*x;
        }
        inline int read()
        {
        bool flag=0;
        char ch=getchar();
        if(ch=='-')
        flag^=1;
        while(!isdigit(ch))
        {
        ch=getchar();
        if(ch=='-')
        flag^=1;
        }
        int sum=ch-'0';
        ch=getchar();
        while(isdigit(ch))
        {
        sum=sum*10+ch-'0';
        ch=getchar();
        }
        return flag?-sum:sum;
        }
        void write(ll x)
        {
        if(x>=10)
        write(x/10);
        putchar('0'+x%10);
        }
        inline void writen(ll x)
        {
        if(x<0)
        {
        putchar('-');
        write(-x);
        }
        else
        write(x);
        putchar('\n');
        }
        inline int cross(pt A,pt B)
        {
        ld d=A*B;
        if(abs(d)<=eps)
        return 0;
        return d>0?1:-1;
        }
        inline pt intersection(line a,line b)
        {
        pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
        if(cross(A,B)==0)
        return pt(inf,inf);
        ld d=-(B*C)/(B*A);
        return b.A+A*d;
        }
        inline int onClockwise(line a,line b,line c)
        {
        return cross(a.B-a.A,intersection(b,c)-a.A)==-1;
        }
        bool cmpR(line A,line B)
        {
        if(A.slope==B.slope)
        return A.b<B.b;
        return A.slope<B.slope;
        }
        bool cmpL(line A,line B)
        {
        if(A.slope==B.slope)
        return A.b>B.b;
        return A.slope<B.slope;
        }
        void initR()
        {
        sort(s+1,s+n+1,cmpR);
        int L=1,R=0;
        for(int i=1;i<=n;++i)
        {
        while(i!=n&&s[i].slope==s[i+1].slope)
        ++i;
        while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
        --R;
        q[++R]=i;
        }
        for(int i=1;i<=R;++i)
        idR[i]=s[q[i]].id;
        for(int i=1;i<R;++i)
        rightPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
        int pos=1;
        for(int i=-base;i<=base;++i)
        {
        while(pos<R&&rightPlane[pos]<ld(i))
        ++pos;
        ans[i+base]=get(i,s[q[pos]].slope,s[q[pos]].b);
        }
        }
        void initL()
        {
        sort(s+1,s+n+1,cmpL);
        int L=1,R=0;
        for(int i=1;i<=n;++i)
        {
        while(i!=n&&s[i].slope==s[i+1].slope)
        ++i;
        while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
        --R;
        q[++R]=i;
        }
        for(int i=1;i<=R;++i)
        idL[i]=s[q[i]].id;
        for(int i=1;i<R;++i)
        leftPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
        int pos=1;
        for(int i=base;i>=-base;--i)
        {
        while(pos<R&&ld(i)<leftPlane[pos])
        ++pos;
        ans[i+base]=max(ans[i+base],get(i,s[q[pos]].slope,s[q[pos]].b));
        }
        }
        int main()
        {
        //    freopen("A.in","r",stdin);
        //    freopen("A.out","w",stdout);
        ios::sync_with_stdio(false);
        n=read(),T=read();
        for(int i=1;i<=n;++i)
        {
        a[i]=read(),b[i]=read();
        s[i].A=pt(0,b[i]);
        s[i].B=pt(1,a[i]+b[i]);
        s[i].slope=a[i];
        s[i].b=b[i];
        s[i].id=i;
        }
        initR();
        for(int i=1;i<=n;++i)
        swap(s[i].A,s[i].B);
        initL();
        while(T--)
        {
        int x=read();
        writen(ans[x+base]);
        }
        return 0;
        }
        
        • 1

        信息

        ID
        54
        时间
        1000ms
        内存
        256MiB
        难度
        5
        标签
        (无)
        递交数
        85
        已通过
        25
        上传者