16级第二周寒假作业B题

Line belt

TimeLimit:1000MS MemoryLimit:32768KB

64-bit integer IO format:%I64d

Problem Description

In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww's speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane.
How long must he take to travel from A to D?

在二维平面中有两条线段AB和CD，lxhgww的速度在AB上是P，在CD上是Q，他可以在平面上的其他区域以速度R移动。
从A到D旅行最少需要多长时间？

Input

The first line is the case number T.
For each case, there are three lines.
The first line, four integers, the coordinates of A and B: Ax Ay Bx By.
The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy.
The third line, three integers, P Q R.
0<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10

第一行是案例编号T.
对于每种情况，有三行。
第一行，四个整数，A和B的坐标：Ax Ay Bx By。
第二行，四个整数，C和D的坐标：Cx Cy Dx Dy。
第三行，三个整数，P Q R
0 <= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy <= 1000
1 <= P，Q，R <= 10

Output

The minimum time to travel from A to D, round to two decimals.

从A运动到D的最短时间，四舍五入到两位小数。（貌似若结果与标准答案误差在0.01以内，是可以AC的）

SampleInput

8
0 0 4 1
4 1 0 2
8 8 1
0 0 0 100
100 0 100 100
2 2 1
8 0 23 8
4 2 91 0
4 9 10
0 0 2 2
0 2 2 0
4 3 1
1 8 1000 10
0 689 10 1000
90 1 20
4 9 4 20
4 41 4 60
4 4 1
4 9 4 20
4 91 4 60
4 3 1
0 5 8 5
2 5 4 0
6 9 3
SampleOutput

1.03
136.60
8.30
0.83
49.60
28.50
42.75
0.93

思路：

根据题意我们可以列出式子time=ab/p+cd/q+bc/r;ab表示在线段AB上运动的距离，cd在线段CD上运动距离，bc表示从线段AB到CD运动的距离。可以看出来，这个式子是一个凹形函数，而time2=cd/q+bc/r也是一个凹形函数，而这个式子其实只有ab，cd两个未知量，所以我们可以用两次三分求解。把登时写为time=ab/p+time2.首先对ab三分，再对cd三分求time2，就可以求出答案。

ps:在这种求解方法中，中间运用了比较多的除法，导致精度损失，所以再开平方前加一个eps，防止开平方后的值比真实值小。

附上我的两个三分代码：

double sanfen(double x)
{
    double time=x/p;
    AX=ax+x/AB*(bx-ax);
    AY=ay+x/AB*(by-ay);
    CD=juli(cx,cy,dx,dy);
    double l=0,r=CD;
    double midl,midr;
    while(r-l>=eps)
    {
        midl=l+(r-l)/3;
        midr=r-(r-l)/3;
        if(getans(midl)>=getans(midr))
            l=midl;
        else
            r=midr;
    }
    return getans((midl+midr)/2)+time;
}
double sanfen2(double l,double r)
{
    double midl,midr;
    while(r-l>=eps)
    {
        midl=l+(r-l)/3;
        midr=r-(r-l)/3;
        if(sanfen(midl)>=sanfen(midr))
            l=midl;
        else
            r=midr;
    }
    return sanfen((midl+midr)/2);
}