洛谷P2571.传送带

洛谷P2571.传送带

• 三分模板题

• 用于单峰函数求极值

  • 一定可以将答案路径分成三段
  • 即AE - EF - FD (E和A可能重复，F和D可能重合)
    • E在线段AB上，F在线段CD上
  • 因为有两个不定点EF，因此假设E为参数，三分求F的位置
  • 再外层三分求E的位置
  • 

•   #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const double eps=1e-8;
    double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
    double dis(double x1,double y1,double x2,double y2)
    {
        double x_dis = x2 - x1 ,y_dis = y2 - y1;
        return sqrt(x_dis*x_dis + y_dis*y_dis);
    }
    //上图中f函数 用于三分找F
    double f(double x1,double y1,double x2,double y2)
    {
        return dis(x1,y1,x2,y2)/r + dis(x2,y2,dx,dy)/q;
    }
    double calc1(double x,double y)  //同理三分
    {
        double lx=cx,ly=cy,rx=dx,ry=dy;
        while(dis(lx,ly,rx,ry)>eps)
        {
            double tmpx = (rx - lx) / 3,tmpy = (ry - ly) / 3;
            //左三等分点 和 右三等分点
            double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy;
            double ans1=f(x,y,lmidx,lmidy),ans2=f(x,y,rmidx,rmidy);
            if(ans2 - ans1 > eps) rx = rmidx,ry = rmidy;
            else lx = lmidx,ly = lmidy;
        }
        return f(x,y,lx,ly);
    }
    double calc()
    {
        //三分
        double lx=ax,ly=ay,rx=bx,ry=by;
        //两点不重合
        while(dis(lx,ly,rx,ry)>eps)
        {
            //x和y的三等分间距
            double tmpx = (rx - lx) / 3,tmpy = (ry - ly) / 3;
            //左三等分点 和 右三等分点
            double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy;
            //左右两点各求一次答案
            double ans1=calc1(lmidx,lmidy) + dis(ax,ay,lmidx,lmidy)/p;
            double ans2=calc1(rmidx,rmidy) + dis(ax,ay,rmidx,rmidy)/p;
            //ans1更小，就是更优，往左收缩区间
            if(ans2 - ans1 > eps) rx = rmidx,ry = rmidy;
            else lx = lmidx,ly = lmidy;
        }
        return calc1(lx,ly) + dis(ax,ay,lx,ly)/p;
    }
    int main(){
    	cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r;
    	
    	printf("%.2lf\n",calc());
    }