题解 P2571 【[SCOI2010]传送带】

· · 题解

这是一道三分的模板题。

其实我瞥了一眼题解才发现是三分

至少学会了一个套路。

AC后看了看题解，5篇中就2篇是三分，结果一篇没有 \LaTeX 真不爽，一篇就一点点代码……

不多说了，开始。

题目大意：

你要从 A 点到 D 点。有两条传送带：第一条从 A 到 B，速度为 p，第二条从 C 到 D，速度为 q。不走传送带时速度为 r。求从 A 到 D 的最少时间。

明显这条路径应该是三条线段组成的：AE+EF+FD。其中 E 在 AB 上，F 在 CD 上。

（以下设 dis(X,Y) 为 X 和 Y 的距离）

那么答案就是 dis(A,E)/p+dis(E,F)/r+dis(F,D)/q。

这实际上是一个二元函数，想要求最小值还比较麻烦。

假设我们把其中一个元（这里取 E）当做参数会怎么样？

那么就是要找一点 F 使得 dis(E,F)/r+dis(F,D)/q 最小。

（以下设 f(X)=(dis(X,F)/r+dis(F,D)/q)_{min}）

容易发现这是个单峰或者单调函数。

有几何画板或者GeoGebra的自己试一下吧，我也说不太清楚……

反正就是 f(E) 是可以通过三分 F 得到最小值的。

但是其实 E 也是个未知量啊！那怎么取得 dis(A,E)/p+f(E) 的最小值呢？

我们发现这也是个单峰或单调函数。可以再三分 E 得出这个最小值，也就是答案。

综上：这题就是三分套三分。

上代码：（详细注释）

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;  //我一般喜欢把eps设为1e-8，当然对于这题1e-6足够了
double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
double dis(double x_1,double y_1,double x_2,double y_2){    //P1和P2的距离
    double xdis=x_1-x_2,ydis=y_1-y_2;
    return sqrt(xdis*xdis+ydis*ydis);
}
double f(double x_1,double y_1,double x_2,double y_2){  //上文中提到的f(P1)在当F是P2时的值
    return dis(x_1,y_1,x_2,y_2)/r+dis(x_2,y_2,dx,dy)/q;
    //第一个是dis(E,F)/r，第二个是dis(F,D)/q
}
double calc1(double x,double y){    //内层三分F（这个给定的参数是固定E是这个点）
    double lx=cx,ly=cy,rx=dx,ry=dy; //在CD上三分
    while(dis(lx,ly,rx,ry)>eps){    //还没有重合成一点
        double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;
        double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy; //(lmidx,lmidy)是左等分点，(rmidx,rmidy)是右等分点
        double 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);    //返回这个最小值
}
double calc(){  //外层三分E
    double lx=ax,ly=ay,rx=bx,ry=by; //在AB上三分
    while(dis(lx,ly,rx,ry)>eps){
        double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;
        double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy; //以上同理
        double ans1=calc1(lmidx,lmidy)+dis(ax,ay,lmidx,lmidy)/p,ans2=calc1(rmidx,rmidy)+dis(ax,ay,rmidx,rmidy)/p;   //左等分点和右等分点的值（在这里套了内层三分）
        if(ans2-ans1>eps) rx=rmidx,ry=rmidy;
        else lx=lmidx,ly=lmidy; //同理
    }
    return calc1(lx,ly)+dis(ax,ay,lx,ly)/p; //返回最小值，也就是答案
}
int main(){
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy,&p,&q,&r);
    printf("%.2lf\n",calc());   //这就是答案
}