bzoj 3203: [Sdoi2013]保护出题人

.

题意：不想概括
题解：凸包+三分
一开始用僵尸过来的顺序处理，推出个式子$y_i\geq\frac{sum_j}{x_i+d(j-1)}(j\leq i)$，然后就不会做了。。。
膜了一堆题解。
用输入的顺序处理血量的前缀和（即入侵房子的后缀和）。那么$y_i\geq\frac{sum_i-sum_{j-1}}{x_i+d(i-j)}$（此处sum与上一段的不同）$y_i=max\left\lbrace\frac{sum_i-sum_{j-1}}{x_i+di-dj}\right\rbrace$这就是个斜率的式子。每加入一个僵尸，就加一个$(dj,sum_{j−1})$的点，然后求所有点中与$(x_i+di,sum_i)$构成直线斜率最大的。因为$(x_i+di,sum_i)$肯定在$(dj,sum_j−1)$的右上角，所以答案肯定在点的下凸包中。在上面三分就好了。
我居然三分都可以打错。。。
代码：

#include<bits/stdc++.h>
using namespace std;
long long n,d,sum[100010],X[100010];
struct pnt
{
    long long x,y;
    pnt(const long long &x=0,const long long &y=0):x(x),y(y){}
}hull[100010];
int sz=0;
double ans=0;
long long multi(const pnt &p0,const pnt &p1,const pnt &p2)
{
    long long x1=p1.x-p0.x,y1=p1.y-p0.y,x2=p2.x-p0.x,y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}
void insert(const pnt &x)
{
    while(sz>1&&multi(x,hull[sz],hull[sz-1])>0)
    sz--;
    hull[++sz]=x;
}
double slp(const pnt &x,const pnt &y)
{
    return 1.0*(x.y-y.y)/(x.x-y.x);
}
double wk(const pnt &x)
{
    int l=1,r=sz;
    while(r-l>=3)
    {
        int m1=l+(r-l)/3,m2=l+2*(r-l)/3;
        // printf("m1:%d slp:%lf m2:%d slp:%lf\n",m1,slp(x,hull[m1]),m2,slp(x,hull[m2]));
        if(slp(x,hull[m1])>slp(x,hull[m2]))
        r=m2;
        else
        l=m1;
    }
    return max(max(slp(x,hull[l]),slp(x,hull[r])),slp(x,hull[l+r>>1]));
}
int main()
{
    scanf("%lld%lld",&n,&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&sum[i],&X[i]);
        sum[i]+=sum[i-1];
    }
    insert(pnt(d,0LL));
    ans=1.0*sum[1]/X[1];
    for(int i=2;i<=n;i++)
    {
        insert(pnt(d*i,sum[i-1]));
        ans+=wk(pnt(X[i]+d*i,sum[i]));
        // printf("%lf\n",wk(pnt(X[i]+d*i,sum[i])));
    }
    printf("%.0lf",ans);
}