P2571 [SCOI2010]传送带

2018-09-11 15:55:25


题意:二维平面上有两条线段,在 $AB$ 上的移动速度为 $p$ ,在 $CD$ 上的移动速度为 $q$ ,在平面上的移动速度 $v$ 。现在从 $A$ 点走到 $D$ 点,最少需要多长时间


要不是loli考三分我还真不知道三分的用处是啥qwq

其实就是用来求单峰函数的极值

对于这道题,ta的路径显然是先在 $AB$ 上走到一点 $E$ ,然后在平面上走到 $CD$ 上一点 $F$ ,再从 $F$ 走到 $D$

那么答案就是 $|AE|/p+|EF|/v+|FD|/q$

这是一个二元函数,不方便直接求解

那就固定一个值,把它变成一个一元函数

固定一个参数 $E$ ,记 $f(E)=|EF|/v+|FD|/q$

画图可以发现它是一个单峰函数

答案为 $Ans=|AE|/p+f(E)$ ,这又是一个单峰函数

所以这题正解就是三分套三分了qwq

把 $eps$ 尽量设小一点,防止卡精度

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double db;
const db eps=1e-8,inf=1e9;
db ax,ay,bx,by,cx,cy,dx,dy,p,q,v;
db getdis(db x,db y,db xx,db yy){return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));}
db F(db x,db y,db xx,db yy){return getdis(x,y,xx,yy)/v+getdis(xx,yy,dx,dy)/q;}
db calc1(db x,db y)
{
    db lx=cx,ly=cy,rx=dx,ry=dy;
    while (getdis(lx,ly,rx,ry)>=eps)
    {
        db tmpx=(rx-lx)/3.0,tmpy=(ry-ly)/3.0;
        db lmidx=lx+tmpx,rmidx=rx-tmpx;
        db lmidy=ly+tmpy,rmidy=ry-tmpy;
        db ans1=F(x,y,lmidx,lmidy),ans2=F(x,y,rmidx,rmidy);
        if (ans2-ans1>=eps) rx=rmidx,ry=rmidy;
        else lx=lmidx,ly=lmidy;
    }
    return F(x,y,lx,ly);
}
db calc()
{
    db lx=ax,ly=ay,rx=bx,ry=by;
    while (getdis(lx,ly,rx,ry)>eps)
    {
        db tmpx=(rx-lx)/3.0,tmpy=(ry-ly)/3.0;
        db lmidx=lx+tmpx,rmidx=rx-tmpx;
        db lmidy=ly+tmpy,rmidy=ry-tmpy;
        db ans1=calc1(lmidx,lmidy)+getdis(ax,ay,lmidx,lmidy)/p;
        db ans2=calc1(rmidx,rmidy)+getdis(ax,ay,rmidx,rmidy)/p;
        if (ans2-ans1>=eps) rx=rmidx,ry=rmidy;
        else lx=lmidx,ly=lmidy;
    }
    return calc1(lx,ly)+getdis(ax,ay,lx,ly)/p;
}
int main()
{
    scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
    scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
    scanf("%lf%lf%lf",&p,&q,&v);
    printf("%.2lf\n",calc());
    return 0;
}