学步园

题意：给出两条平行的线段AB， CD，然后一个人在线段AB的A点出发，走向D点，其中，人在线段AB上的速度为P， 在线段CD上的速度为Q，在其他地方的速度为R，求人从A点到D点的最短时间。

分析：居然要用三分，哎，怎么也没想到，先在AB上三分，固定一个点，接着在CD上三分，就是嵌套的三分搜索，思路清晰的话，代码也不是很难敲

注意精度还有边界的处理

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
struct point
{
double x,y;
};
point A,B,C,D;
int p,q,r;
double length(point X,point Y)
{
return sqrt((X.x-Y.x)*(X.x-Y.x)+(X.y-Y.y)*(X.y-Y.y));
}
double time(double a,double b)
{
    point X,Y;
    X.x=a*(B.x-A.x)+A.x;
    X.y=a*(B.y-A.y)+A.y;
    Y.x=b*(C.x-D.x)+D.x;
    Y.y=b*(C.y-D.y)+D.y;
return length(A,X)/p+length(D,Y)/q+length(X,Y)/r;
}
double ThiDiv(double lena)
{
double left=0.0,right=1.0,lm,rm;
while(right-left>1e-6)
    {
        lm=(left*2.0+right)/3.0;
        rm=(left+right*2.0)/3.0;
if(time(lena,lm)<=time(lena,rm))
            right=rm;
else left=lm;
    }
return time(lena,left);
}
int main()
{
int T;
    scanf("%d",&T);
while(T--)
    {
        scanf("%lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y);
        scanf("%lf %lf %lf %lf",&C.x,&C.y,&D.x,&D.y);
        scanf("%d %d %d",&p,&q,&r);
double left=0.0,right=1.0,lm,rm;
while(right-left>1e-6)//这个大于号居然写出了小于号，测试例子居然也过了，WA了N次
        {
//这里三分的是在AB上走的距离占AB比例
            lm=(left*2+right)/3.0;
            rm=(left+2*right)/3.0;
if(ThiDiv(lm)<=ThiDiv(rm))
                right=rm;
else left=lm;
        }
        printf("%.2f\n",ThiDiv(left));
    }
return 0;
}