首页 > 其他 > 详细

bzoj 2876: [Noi2012]骑行川藏【拉格朗日乘数法+二分】

时间:2018-02-19 10:06:49      阅读:86      评论:0      收藏:0      [点我收藏+]

标签:put   ++   inline   -s   include   -m   source   b+   href   

详见:
http://blog.csdn.net/popoqqq/article/details/42366599
http://blog.csdn.net/whzzt/article/details/51346228
用拉格朗日乘数法,求了偏导之后二分λ。然后求完偏导的那个一元三次式的解可以二分求,因为是单调递增的。
总复杂度\( O(nlog^2n) \)

#include<cstdio>
#include<cmath>
using namespace std;
const int N=120005;
int n,q,op,i,m;
double X1,X2,Y1,Y2,a,b,c,d,aa[N],bb[N],cc[N],ab[N],ac[N],bc[N],saa,sbb,scc,sab,sac,sbc,eps=1e-8,ans;
inline bool cmp(double x)
{
    return fabs(x)<eps;
}
inline double solve(double a,double b,double c)
{
    if(cmp(a))
        return c;
    double x=-b/(2.0*a);
    return a*x*x+b*x+c;
}
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&op);
        if(op==0)
        {
            scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
            if(cmp(X1-X2))
                a=1,b=0,c=-X1;
            else 
                a=(Y2-Y1)/(X2-X1),b=-1,c=Y1-a*X1;
            d=a*a+b*b;
            aa[++n]=a*a/d,bb[n]=b*b/d,cc[n]=c*c/d,ab[n]=a*b/d,ac[n]=a*c/d,bc[n]=b*c/d;
            saa+=aa[n],sbb+=bb[n],scc+=cc[n],sab+=ab[n],sac+=ac[n],sbc+=bc[n];
            m++;
        }
        if(op==1)
        {
            scanf("%d",&i);
            saa-=aa[i],sbb-=bb[i],scc-=cc[i],sab-=ab[i],sac-=ac[i],sbc-=bc[i];
            m--;
        }
        if(op==2)
        {
            if(!m)
            {
                puts("0.00");
                continue;
            }
            if(cmp(sbb))
                a=b=0;
            else 
                a=-sab/sbb,b=-sbc/sbb;
            ans=solve(saa+2.0*a*sab+a*a*sbb,2.0*(b*sab+sac+a*b*sbb+a*sbc),b*b*sbb+2.0*b*sbc+scc);
            if(cmp(ans))
                ans=0;
            printf("%.2f\n",ans);
        }
    }
    return 0;
}

bzoj 2876: [Noi2012]骑行川藏【拉格朗日乘数法+二分】

标签:put   ++   inline   -s   include   -m   source   b+   href   

原文:https://www.cnblogs.com/lokiii/p/8453515.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号