BZOJ-1857: [Scoi2010]传送带

[文章目录]

Description

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

三分套三分。
如果确定在AB离开的地方,答案是关于在CD线段上开始的地方的单峰函数,同时,最优答案也是关于AB离开的地方的单峰函数。先三分AB离开的地方,再三分最优答案CD开始的地方即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db;
db ax,ay,bx,by,cx,cy,dx,dy,v1,v2,v3;
db dis(db x1,db y1,db x2,db y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
db getans(db x,db y)
{
    db x1,y1,x2,y2;
    db l=0,r=1,mid1,mid2,len; int t=40;
    while(t--)
    {
        len=(r-l)/3; mid1=l+len; mid2=r-len;
        x1=dx*mid1-cx*mid1+cx;
        x2=dx*mid2-cx*mid2+cx;
        y1=dy*mid1-cy*mid1+cy;
        y2=dy*mid2-cy*mid2+cy;
        if(dis(x,y,x1,y1)/v2+dis(x1,y1,dx,dy)/v3 < 
            dis(x,y,x2,y2)/v2+dis(x2,y2,dx,dy)/v3)
            r=mid2;
        else l=mid1;
    }
    len=(l+r)/2;
    x1=dx*len-cx*len+cx;
    y1=dy*len-cy*len+cy;
    return dis(ax,ay,x,y)/v1+dis(x,y,x1,y1)/v2+dis(x1,y1,dx,dy)/v3;
}
int main()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
    scanf("%lf%lf%lf",&v1,&v3,&v2);
    db l=0,r=1,mid1,mid2,len; int t=40;
    while(t--)
    {
        len=(r-l)/3; mid1=l+len; mid2=r-len;
        if(getans(bx*mid1-ax*mid1+ax,by*mid1-ay*mid1+ay) < 
            getans(bx*mid2-ax*mid2+ax,by*mid2-ay*mid2+ay))
            r=mid2;
        else l=mid1;
    }
    len=(l+r)/2;
    printf("%.2lf\n",getans(bx*len-ax*len+ax,by*len-ay*len+ay));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注