ZROI2018提高day2t1-白红宇

ZROI2018提高day2t1

阅读量：6909 次

发布时间：2019-06-27

本文共 1728 字，大约阅读时间需要 5 分钟。

分析

考场上写了前20分和|a[i]|<=1的情况，但是因为没开long long爆零了。实际考场上差不多想到正解了，至少当时不会凸壳...

我们发现对于ax²+bx的大小关系我们可以将其转换成ax+b，所以我们可以将这些直线求一个上凸壳和一个下凸壳，然后离线处理所有x，对于小于0的x找到下凸壳中这个x对应的值，而如果大于等于0则在上凸壳中找。对于凸壳的构造实际就和求一个边凸包一样，只需要比较第i条边和栈顶边的交点是否小于栈顶边和栈中第二个边的交点然后判断是否弹栈就可以了。注意这个题有一些细节，比如对于b的处理，在a相等时要将b作为第二关键字。详见代码。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                  #include
                 #include
                  
                   using namespace std;const double inf = 40000.0;const double ep = 1e-7;struct node { long long a,b;};struct que { long long x,id;};node d[500100];que X[500100];long long ans[500100],is[500100],be[500100],n,m,last;double fin[500100];stack
                   
                    a;inline bool cmp(const node p,const node q){ if(p.a==q.a)return p.b>q.b; return p.a>q.a;}inline bool cmp1(const node p,const node q){ if(p.a==q.a)return p.b
                    
                     =0)return; if(double(X[j].x)<=fin[i])ans[X[j].id]=d[i].a*X[j].x*X[j].x+d[i].b*X[j].x,last++; else break; } } return;}inline void work(long long wh){ init(); if(wh==-1)sort(d+1,d+n+1,cmp); else sort(d+1,d+n+1,cmp1); a.push(1); is[1]=1; be[1]=0; fin[0]=-inf; for(long long i=2;i<=n;i++){ int ok=1; while(1){ long long x=a.top(); if(fin[be[x]]>getnode(x,i)){ a.pop();is[x]=0; }else break; } be[i]=a.top();fin[a.top()]=getnode(a.top(),i); a.push(i);is[i]=1; if(wh==1)fin[i]=inf; else fin[i]=0; } deal(wh); return;}int main(){ long long i,j,k; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++)scanf("%lld%lld",&d[i].a,&d[i].b); for(i=1;i<=m;i++)scanf("%lld",&X[i].x),X[i].id=i; sort(X+1,X+m+1,cmp2); work(-1);work(1); for(i=1;i<=m;i++)printf("%lld\n",ans[i]);}

转载于:https://www.cnblogs.com/yzxverygood/p/9595386.html

你可能感兴趣的文章