hdu 3430 Line belt【三分嵌套】

二分法作为分治中最常见的方法，适用于单调函数，逼近求解某点的值。但当函数是凸性函数时，二分法就无法适用，这时三分法就可以“大显身手”～～

类似于二分的定义Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2; 如果mid靠近极值点，则Right = midmid；否则(即midmid靠近极值点)，则Left = mid;

程序模版如下：

double Calc(Type a)
{
    /* 根据题目的意思计算 */
}
void Solve(void)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN; Right = MAX;
    while (Left + EPS < Right)
    {
        mid = (Left + Right) / 2;
        midmid = (mid + Right) / 2;
        mid_area = Calc(mid);
        midmid_area = Calc(midmid);
        // 假设求解最大极值.
        if (mid_area >= midmid_area) Right = midmid;
        else Left = mid;
    }
}

t=x/p+y/q+z/r

f(t)=x/p+y/q+z/r;

f(t)=x/p+g(y),g(y)=y/q+z/r;

则g(y)关于y为凸性函数，f(t)关于x,y为凸性函数（可能为递增函数）,所以用两次三分，先在外层取mid,midmid，再每次以mid，midmid为m点对内层用三分求解最小时间g(y),完成外层的三分求解。

此外，这一题要的是对时间的精度，所以精度控制应该为fabs(t1-t2)<eps，而不是right-left<eps,否则可能出现right-left=1e-7,但对应fabs(t1-t2)=0.1的情况！

#include <cstdio>
#include <cmath>
using namespace std;
const double eps=1e-6;
double p,q,r;
struct point{
    double x,y;
}a,b,c,d;
double dis(point a, point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point get_mid(point a,point b){
    a.x=(a.x+b.x)/2,a.y=(a.y+b.y)/2;    return a;
}
double triple_cd(point c, point d, point m)
{
    point mid,midmid;
    point left=c,right=d; 
    double t1,t2;
    do{
        mid=get_mid(left,right);
        midmid=get_mid(mid,right);
        t1=dis(m,mid)/r+dis(d,mid)/q;
        t2=dis(m,midmid)/r+dis(d,midmid)/q;
        t1<t2?right=midmid:left=mid;
    }while(fabs(t1-t2)>=eps);
    return t1;
}    
double triple_ab(point a,point b,point c,point d)
{
    point mid,midmid,left=a,right=b;
    double t1,t2;
    left=a;
    right=b;
    do{
        mid=get_mid(left,right);
        midmid=get_mid(mid,right);
        t1=dis(mid,a)/p+triple_cd(c,d,mid);
        t2=dis(midmid,a)/p+triple_cd(c,d,midmid);
        t1<t2?right=midmid:left=mid;
    }while(fabs(t1-t2)>=eps);
    return t1;
}
int main()
{
    int t;
    scanf("%d",&t);
    double ans;
    while (t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&p,&q,&r);
        ans=triple_ab(a,b,c,d);
        printf("%.2lf\n",ans);
    }
    return 0;
}