首页 > 代码库 > bzoj3203: [Sdoi2013]保护出题人 凸包+三分

bzoj3203: [Sdoi2013]保护出题人 凸包+三分

/**************************************************************    Problem: 3203    User: wangyucheng    Language: C++    Result: Accepted    Time:344 ms    Memory:4396 kb****************************************************************/ #include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;#define N 100003typedef long long ll;int n;double d,a[N],x[N],ans=0.0;struct P{    double x,y;    P(double a=0.0,double b=0.0){     x=a,y=b;       }       P operator-(P b){return P(x-b.x,y-b.y);}    double operator*(P b){return x*b.y-y*b.x;}}s[N];double sp(P a,P b){   return (a.y-b.y)/(a.x-b.x);  }int main(){    scanf("%d",&n);    scanf("%lf",&d);    for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i],&x[i]);    double sum =0;    int top=0;    for(int i=1;i<=n;i++){        P p=P(i*d,sum);sum+=a[i];        while(top>1&&(p-s[top-1])*(s[top]-s[top-1])>=0)top--;        s[++top]=p;        p=P(x[i]+i*d,sum);        int l=1,r=top,m1,m2;        while(r-l>=3){           m1=l+(r-l)/3;           m2=r-(r-l)/3;           double k1=sp(s[m1],p),k2=sp(s[m2],p);           if(k1<k2)l=m1;else r=m2;          }        double res=0;        for(int j=l;j<=r;j++)res=max(res,sp(s[j],p));        ans+=res;             }    printf("%.0lf\n",ans);}