BZOJ-3203: [Sdoi2013]保护出题人

Description

每次只打排在最前面僵尸这个很烦啊。
神奇的思路：对于每个僵尸的血量都加上其前面僵尸的血量（设为s[i]），那么每个僵尸就变成独立的了。
发现答案即为max{s[i]/(x+kd)}。发现是一个斜率的形式。
那么我们把s[i]看做纵坐标，到房子的距离看成横坐标。那么我们就是求一个原点到所有点的最大斜率。拿栈维护凸包，每次二分找原点关于凸包的切线即可。
另外每次加一个僵尸相当于原来所有的点纵坐标加上一个值，横坐标加上一个值，直接移动原点的坐标。
代码奇短

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double ld;
#define N 101000 
int n,top;
ld d;
double ans;
struct point
{
    ld x,y;
    point operator - (const point &z)const {return (point){z.x-x,z.y-y};}
    double calc(const point &z)const {return (y-z.y)/(x-z.x);}
}z[N],o;
int main()
{
    scanf("%d%lf",&n,&d);
    ld x,y; point t; int l,r,mid;
    for(int i=1;i<=n;++i)
    {
        scanf("%lf%lf",&y,&x);
        o=(point){z[top].x-d-x,o.y-y};
        t=(point){o.x+x,o.y+y};
        while(top>1&&t.calc(z[top-1])-t.calc(z[top])>0) top--;
        z[++top]=t; l=1; r=top;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(z[mid+1].calc(o)-z[mid].calc(o)>0) l=mid+1;
            else r=mid;
        }
        ans+=z[l].calc(o);
    }
    printf("%.0lf",ans);
    return 0;
}