首页 > 代码库 > 16级第二周寒假作业B题

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);
}

16级第二周寒假作业B题