首页 > 代码库 > 传送带(bzoj 1857)

传送带(bzoj 1857)

Description

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间

Input

输入数据第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By 第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy 第三行是3个整数,分别是P,Q,R

Output

输出数据为一行,表示lxhgww从A点走到D点的最短时间,保留到小数点后2位

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

HINT

对于100%的数据,1<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

/*
    路线可以分为三部分:在AB上的,CD上的,还有在平面上的。
    可以三分AB上的断点和CD上的断点。 
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-9
using namespace std;
double ax,ay,bx,by,cx,cy,dx,dy,P,Q,R,ans;
double calc(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double sa2(double x,double y){//CD无斜率
    double m1,m2,k,t1,t2,l,r;
    l=min(cy,dy),r=max(cy,dy);
    while(l+eps<r){
        m1=(2*l+r)/3,m2=(l+2*r)/3;
        t1=calc(cx,m1,dx,dy)/Q+calc(cx,m1,x,y)/R;
        t2=calc(cx,m2,dx,dy)/Q+calc(cx,m2,x,y)/R;
        if(t1<t2) r=m2;
        else l=m1;
    }
    t1=calc(cx,l,dx,dy)/Q+calc(cx,l,x,y)/R;
    return t1;
}
double sanfen2(double x,double y){//CD有斜率
    if(cx==dx) return sa2(x,y);
    double m1,m2,k,t1,t2,l,r,b;
    l=min(cx,dx),r=max(cx,dx);
    k=(cy-dy)/(cx-dx);
    b=cy-k*cx;
    while(l+eps<r){
        m1=(2*l+r)/3,m2=(l+2*r)/3;
        t1=calc(m1,m1*k+b,dx,dy)/Q+calc(m1,m1*k+b,x,y)/R;
        t2=calc(m2,m2*k+b,dx,dy)/Q+calc(m2,m2*k+b,x,y)/R;
        if(t1<t2) r=m2;
        else l=m1;
    }
    t1=calc(l,l*k+b,dx,dy)/Q+calc(l,l*k+b,x,y)/R;
    return t1;
}
void sanfen1(){//AB有斜率
    double m1,m2,k,t1,t2,l,r,b;
    l=min(ax,bx),r=max(ax,bx);
    k=(ay-by)/(ax-bx);
    b=ay-k*ax;
    while(l+eps<r){
        m1=(2*l+r)/3,m2=(l+2*r)/3;
        t1=sanfen2(m1,k*m1+b)+calc(m1,m1*k+b,ax,ay)/P;
        t2=sanfen2(m2,m2*k+b)+calc(m2,m2*k+b,ax,ay)/P;
        if(t1<t2) r=m2;
        else l=m1;
    }
    t1=sanfen2(l,l*k+b)+calc(l,l*k+b,ax,ay)/P;
    ans=min(ans,t1);
}
void sa1(){//AB无斜率.
    double m1,m2,k,t1,t2,l,r;
    l=min(ay,by),r=max(ay,by);
    while(l+eps<r){
        m1=(2*l+r)/3,m2=(l+2*r)/3;
        t1=sanfen2(ax,m1)+calc(ax,m1,ax,ay)/P;
        t2=sanfen2(ax,m2)+calc(ax,m2,ax,ay)/P;
        if(t1<t2) r=m2;
        else l=m1;
    }
    t1=sanfen2(ax,l)+calc(ax,l,ax,ay)/P;
    ans=min(ans,t1);
}
int main(){
    cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy;
    cin>>P>>Q>>R;
    ans=calc(ax,ay,dx,dy)/R;
    if(ax!=bx) sanfen1();
    else sa1();
    printf("%.2lf",ans);
    return 0;
}

 

传送带(bzoj 1857)