BZOJ1857:[Scoi2010]传送带 三分

思路:

显然一条比较优的路径是从\(A\)走到\(AB\)上一点\(X\),然后从\(X\)走到\(CD\)上一点\(Y\),然后从\(Y\)走到\(D\).

关键是\(X,Y\)如何确定.

我们能够发现\(X\)点确定时,随着\(Y\)的移动,总路程是一个单峰函数.

更加神奇的是,随着\(X\)的移动,通过我们上述三分得到的总路程也是一个单峰函数!

没什么说的,三分套三分就行了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define eps 1e-8
struct Point{
    f2 x,y;
    void read(){scanf("%lf%lf",&x,&y);}
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
}A,B,C,D;
 
int vab,vcd,vplane;
 
f2 sqr(const f2&x){return x*x;}
f2 Dist(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
f2 f(Point x,Point l,Point v,f2 k){
    return Dist(x,l+v*k)/vplane+Dist(l+v*k,l+v)/vcd;
}
f2 Solve(Point x,Point l,Point r){
    Point v=l-r;
    f2 L=0,R=1,LL,RR,ansl,ansr,lastans=1e12,nowans;
    while(1){
        LL=L+(R-L)/3,RR=R-(R-L)/3;
        ansl=f(x,l,v,LL),ansr=f(x,l,v,RR);
        if(ansl<ansr)R=RR,nowans=ansl;else L=LL,nowans=ansr;
        if(fabs(nowans-lastans)<1e-5)break;lastans=nowans;
    }
    return lastans;
}
 
int main(){
    A.read(),B.read(),C.read(),D.read();
    scanf("%d%d%d",&vab,&vcd,&vplane);
    f2 L=0,R=1,LL,RR,ansl,ansr,lastans=1e12,nowans;Point v=A-B;
    while(1){
        LL=L+(R-L)/3,RR=R-(R-L)/3;
        ansl=Dist(A,A+v*LL)/vab+Solve(A+v*LL,C,D),ansr=Dist(A,A+v*RR)/vab+Solve(A+v*RR,C,D);
        if(ansl<ansr)R=RR,nowans=ansl;else L=LL,nowans=ansr;
        if(fabs(nowans-lastans)<1e-5)break;lastans=nowans;
    }
    printf("%.2lf",lastans);
    return 0;
}