[三分]bzoj1857: [Scoi2010]传送带

题目描述

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

输入

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

输出

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

样例输入

0 0 0 100
100 0 100 100
2 2 1

样例输出

136.60

提示

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

来源

Day2

题解

瞎几把分析一波,可以发现在AB​上去一点E​,在CD​上取一点F​,肯定会有E​F​使得A\to E\to F\to D​的距离最短;

那么我们先三分一下在AB上的x值,再三分一下CD上的x值,计算一波即可;

注意如果AxBx相等,那么三分y值,如果Ax>Bx那么要swap一下,CD同理;预先计算一下两个端点的值,因为可能会有Ax=Bx=Ay=By这样的情况;

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
    int Res=0,f=1;char ch=getchar();
    while (ch>'9'||ch<'0') f=(ch=='-')?-f:f,ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res*f;
}
double eps=1e-4;
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
double Ak,Ab,Ck,Cb,P,Q,R;
bool visA=0,visB=0;
#define sqr(x) ((x)*(x))
double check(double wx,double wy,double x){
    double y=Ck*x+Cb;
    if (visB) y=x,x=Cx;
    double dis=sqrt(sqr(wx-x)+sqr(wy-y))/R+sqrt(sqr(x-Dx)+sqr(y-Dy))/Q;
    return dis;
}
double calc(double x){
    double y=Ak*x+Ab;
    double l=Cx,r=Dx,m1,m2,Min=1e99;
    if (visA) y=x,x=Ax;
    double dis=sqrt(sqr(x-Ax)+sqr(y-Ay))/P;
    if (visB) l=Cy,r=Dy;
    if (l>r) swap(l,r);
    Min=min(check(x,y,l),check(x,y,r));
    while (r-l>=eps){
        m1=l+(r-l)/3;m2=r-(r-l)/3;
        double A=check(x,y,m1),B=check(x,y,m2);
        Min=min(Min,min(A,B));
        if (A<=B) r=m2;else l=m1;
    }
    return Min+dis;
}
int main()
{
    scanf("%lf%lf%lf%lf",&Ax,&Ay,&Bx,&By);
    if (Ax==Bx) visA=1;else Ak=(Ay-By)/(Ax-Bx);Ab=Ay-Ax*Ak;
    scanf("%lf%lf%lf%lf",&Cx,&Cy,&Dx,&Dy);
    if (Cx==Dx) visB=1;else Ck=(Cy-Dy)/(Cx-Dx);Cb=Cy-Cx*Ck;
    scanf("%lf%lf%lf",&P,&Q,&R);
    double l=Ax,r=Bx,m1,m2,Min=1e99;
    if (visA) l=Ay,r=By;
    if (l>r) swap(l,r);
    Min=min(calc(l),calc(r));
    while (r-l>=eps){
        m1=l+(r-l)/3;m2=r-(r-l)/3;
        double A=calc(m1),B=calc(m2);
        Min=min(Min,min(A,B));
        if (A<=B) r=m2;else l=m1;
    }
    printf("%.2lf\n",Min);
    return 0;
}
0 Comments
Leave a Reply