Bzoj 1857: [Scoi2010]传送带(三分套三分)

1857: [Scoi2010]传送带

Time Limit: 1 Sec Memory Limit: 64 MB

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

Source

Day2

/*

三分套三分.

比较显然的凸形函数.

凸性函数套凸性函数应该还是凸性函数吧....

不会证明.

别忘了讨论斜率为0的情况....

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#define MAXN 10001

#define eps 1e-9

using namespace std;

double ax,ay,bx,by,cx,cy,dx,dy,P,Q,R,ans;

double Cola(double x1,double y1,double x2,double y2)

{

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

double sanfenfuben2(double x,double y)//CD无斜率.

{

    double mid,midmid,k,t1,t2,l,r;

    l=min(cy,dy),r=max(cy,dy);

    while(l+eps<r)

    {

        mid=(2*l+r)/3,midmid=(l+2*r)/3;

        t1=Cola(cx,mid,dx,dy)/Q+Cola(cx,mid,x,y)/R;

        t2=Cola(cx,midmid,dx,dy)/Q+Cola(cx,midmid,x,y)/R;

        if(t1<t2) r=midmid;

        else l=mid;

    }

    t1=Cola(cx,l,dx,dy)/Q+Cola(cx,l,x,y)/R;

    return t1;

}

double sanfen2(double x,double y)//CD有斜率.

{

    if(cx==dx) return sanfenfuben2(x,y);

    double mid,midmid,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)

    {

        mid=(2*l+r)/3,midmid=(l+2*r)/3;

        t1=Cola(mid,mid*k+b,dx,dy)/Q+Cola(mid,mid*k+b,x,y)/R;

        t2=Cola(midmid,midmid*k+b,dx,dy)/Q+Cola(midmid,midmid*k+b,x,y)/R;

        if(t1<t2) r=midmid;

        else l=mid;

    }

    t1=Cola(l,l*k+b,dx,dy)/Q+Cola(l,l*k+b,x,y)/R;

    return t1;

}

void sanfen1()//AB有斜率.

{

    double mid,midmid,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)

    {

        mid=(2*l+r)/3,midmid=(l+2*r)/3;

        t1=sanfen2(mid,k*mid+b)+Cola(mid,mid*k+b,ax,ay)/P;//+Cola(mid,mid*k,dx,dy)/R;

        t2=sanfen2(midmid,midmid*k+b)+Cola(midmid,midmid*k+b,ax,ay)/P;//+Cola(midmid,midmid*k,dx,dy)/R;

        if(t1<t2) r=midmid;

        else l=mid;

    }

    t1=sanfen2(l,l*k+b)+Cola(l,l*k+b,ax,ay)/P;

    ans=min(ans,t1);

}

void sanfenfuben1()//AB无斜率.

{

    double mid,midmid,k,t1,t2,l,r;

    l=min(ay,by),r=max(ay,by);

    while(l+eps<r)

    {

        mid=(2*l+r)/3,midmid=(l+2*r)/3;

        t1=sanfen2(ax,mid)+Cola(ax,mid,ax,ay)/P;//+Cola(mid,mid*k,dx,dy)/R;

        t2=sanfen2(ax,midmid)+Cola(ax,midmid,ax,ay)/P;//+Cola(midmid,midmid*k,dx,dy)/R;

        if(t1<t2) r=midmid;

        else l=mid;

    }

    t1=sanfen2(ax,l)+Cola(ax,l,ax,ay)/P;

    ans=min(ans,t1);

}

int main()

{

    freopen("walk.in","r",stdin);

    freopen("walk.out","w",stdout);

    cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy;

    cin>>P>>Q>>R;

    ans=Cola(ax,ay,dx,dy)/R;

    if(ax!=bx) sanfen1();

    else sanfenfuben1();

    printf("%.2lf",ans);

    return 0;

}

巴特西

Bzoj 1857: [Scoi2010]传送带(三分套三分)

最新文章

热门文章