首页 > 代码库 > 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);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。