三分算法！！！！-JZTXT

意思就是有两个传送带在xy坐标轴中，一个是a到b的传送带，一个是c到d的传送带，然后跟你3个速度，问你最短时间从a到d点。

三分算法与二分的区别在与二分是用一个中点求值且必须在一个单调的线段上，而三分就是在一个存在峰值的线段上通过三等分找到峰值在哪里。

题解：首先最短距离应该是在ab上的一个点到cd上的一个点然后在到d点，这个是最快的。但是这两个点我们不知道，要快速找出这两个点就需要用到三分算法，和二分类似。

首先我们先去三分a到b然后把三等分点放到c到d的三方中在c到d找出一个点让ab来到cd的距离尽可能短，判断就是ab的点来到cd的点加上到d的距离即可，一点点缩小三分范围，求出最优点；

然后又回到ab的三分循环，利用a到ab点的距离加上刚刚的最优点距离判断，看看这两个ab的三分点谁最优然后在进行变换区间，一个个全部枚举完就可以了。

代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define int long long
using namespace std;
const double eps=1e-8;
struct G{
    double x,y;
};
G a,b,c,d;
int p,q,r1;
double ans=1e8;
double dis(G l,G r)
{
    return sqrt((l.x-r.x)*(l.x-r.x)+(l.y-r.y)*(l.y-r.y));
}
double f(G mid ,G midmid)
{
    return dis(mid,midmid)/r1+dis(midmid,d)/q;
}
double cd(G mid1)
{
    double N;
    G l,r;
    l.x=c.x,l.y=c.y;
    r.x=d.x,r.y=d.y;
    do{
        G mid, midmid;
        mid.x = (l.x + r.x) / 2.0;
        mid.y = (l.y + r.y) / 2.0;
        midmid.x = (mid.x + r.x) / 2, 0;
        midmid.y = (mid.y + r.y) / 2.0;
        if (f(mid1, mid) < f(mid1, midmid)) {
            N=min(ans,f(mid1,mid));
            r=midmid;
        }
        else
        {
            N=min(ans,f(mid1,midmid));
            l=mid;
        }
    } while (dis(l,r)>eps);
    return N;
}
int main()
{
    cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
    cin>>p>>q>>r1;
    G l,r;
    l.x=a.x,l.y=a.y,r.x=b.x,r.y=b.y;
    do
    {
        G mid,midmid;
        mid.x=(l.x+r.x)/2.0;
        mid.y=(l.y+r.y)/2.0;
        midmid.x=(mid.x+r.x)/2.0;
        midmid.y=(mid.y+r.y)/2.0;
        double ans1=cd(mid);
        double ans2=cd(midmid);
        
        ans1+=dis(a,mid)/p;
        ans2+=dis(a,midmid)/p;
        if(ans1<ans2)
        {
            ans=min(ans,ans1);
            r=midmid;
        }
        else
        {
            ans=min(ans,ans2);
            l=mid;
        }
    } while (dis(l,r)>eps);
    printf("%0.2lf",ans);
    return 0;
}