BZOJ1857 Scoi2010 传送带

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

三分套三分

#include<bits/stdc++.h>

using namespace std;

#define eps 1e-3

int ax,ay,bx,by,cx,cy,dx,dy;

int p,q,r;

double dis(double x1,double y1,double x2,double y2){

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

}

double calc(double x,double y){

    double lx=cx,ly=cy,rx=dx,ry=dy;

    while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){

        double x1=lx+(rx-lx)/3,y1=ly+(ry-ly)/3;

        double x2=rx-(rx-lx)/3,y2=ry-(ry-ly)/3;

        double t1=dis(ax,ay,x,y)/p+dis(x,y,x1,y1)/r+dis(x1,y1,dx,dy)/q;

        double t2=dis(ax,ay,x,y)/p+dis(x,y,x2,y2)/r+dis(x2,y2,dx,dy)/q;

        if(t1<t2)rx=x2,ry=y2;

        else lx=x1,ly=y1;

    }

    return dis(ax,ay,x,y)/p+dis(x,y,lx,ly)/r+dis(lx,ly,dx,dy)/q;

}

int main(){

    cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r;

    double lx=ax,ly=ay,rx=bx,ry=by;

    while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){

        double x1=lx+(rx-lx)/3,y1=ly+(ry-ly)/3;

        double x2=rx-(rx-lx)/3,y2=ry-(ry-ly)/3;

        if(calc(x1,y1)<calc(x2,y2))rx=x2,ry=y2;

        else lx=x1,ly=y1;

    }

    printf("%.2lf",calc(lx,ly));

    return 0;

}

巴特西

BZOJ1857 Scoi2010 传送带【三分】

BZOJ1857 Scoi2010 传送带

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

BZOJ1857 Scoi2010 传送带 【三分】

BZOJ1857 Scoi2010 传送带

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

BZOJ1857 Scoi2010 传送带【三分】