HDU 3400 Line belt

Line belt

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3925    Accepted Submission(s): 1524

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?

 

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

 

Output

 

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

 

Sample Input

 

1

0 0 0 100

100 0 100 100

2 2 1

 

Sample Output

 

136.60

 

三分法求解问题，奇怪的是 do{}while();过， while(){}不过；

AC代码：

# include <bits/stdc++.h>
using namespace std;
const double eps = 1e-5;
struct Point
{
    double x;
    double y;
};

double dis(Point a, Point b)
{
    return sqrt((b.y - a.y)*(b.y - a.y) + (a.x - b.x)*(a.x - b.x));
}

double p, q, r;
double re2(Point a, Point c, Point d)
{
    Point left, right;
    Point mid, midmid;
    double t1, t2;
    left = c; right = d;
    do
    {
        mid.x = (left.x + right.x) / 2;
        mid.y = (left.y + right.y) / 2;
        midmid.x = (mid.x + right.x) / 2;
        midmid.y = (mid.y + right.y) / 2;
        t1 = dis(a, mid) / r + dis(mid, d) / q;
        t2 = dis(a, midmid) / r + dis(midmid, d) / q;
        if(t1 > t2)
            left = mid;
        else 
            right = midmid;
    }
    while(dis(left, right) >= eps);
    return t1;
}
double re(Point a, Point b, Point c, Point d)
{
    Point l, r;
    Point mid, midmid;
    double t1, t2;
    l = a;
    r = b;
    do
    {
        mid.x = (l.x + r.x) / 2;
        mid.y = (l.y + r.y) / 2;
        midmid.x = (mid.x + r.x) / 2;
        midmid.y = (mid.y + r.y) / 2;
        t1 = dis(a, mid) / p + re2(mid, c, d);
        t2 = dis(a, midmid) / p + re2(midmid, c, d);
        if(t1 > t2)
            l = mid;
        else
            r = midmid;
    }while(dis(l, r) >= eps);
    return t1;
}


int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        Point a, b, c, d;
        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("%lf%lf%lf", &p, &q, &r);
        
        printf("%.2lf
", re(a, b, c, d));
    }
    
    
    return 0;
}