BZOJ1857 [Scoi2010]传送带 【三分法】

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
struct point{
    double x,y;
}A,B,C,D,AB,CD;
inline point operator -(const point& a,const point& b){
    return (point){a.x - b.x,a.y - b.y};
}
inline point operator +(const point& a,const point& b){
    return (point){a.x + b.x,a.y + b.y};
}
inline point operator *(const double& a,const point& b){
    return (point){a * b.x,a * b.y};
}
double dis(const point& a,const point& b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double P,Q,R;
double cal2(double lam1,double lam2){
    point E = A + lam1 * AB,F = C + lam2 * CD;
    return dis(A,E) / P + dis(E,F) / R + dis(F,D) / Q;
}
double cal(double lam){
    double l = 0,r = 1,lmid,rmid,len,cl,cr;
    while (r - l > 0.00001){
        len = r - l;
        lmid = l + len / 3;
        rmid = r - len / 3;
        cl = cal2(lam,lmid); cr = cal2(lam,rmid);
        if (cl > cr) l = lmid;
        else r = rmid;
    }
    return cal2(lam,(r + l) / 2);
}
int main(){
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y,&P,&Q,&R);
    AB = B - A; CD = D - C;
    double l = 0,r = 1,lmid,rmid,len,cl,cr;
    while (r - l > 0.00001){
        len = r - l;
        lmid = l + len / 3;
        rmid = r - len / 3;
        cl = cal(lmid); cr = cal(rmid);
        if (cl > cr) l = lmid;
        else r = rmid;
    }
    printf("%.2lf\n",cal((l + r) / 2));
    return 0;
}