WUSTOJ 2573 传送带 【三分嵌套】

题目来源：http://acm.wust.edu.cn/problem.php?id=2573&soj=0

★这题一开始以为是二分嵌套。。。后来发现不行，就尝试三分，AC ~

相关知识：

二分模板：

double l=0,r=1000;
while(l<=r){
    double mid=(l+r)/2;
    if(f(mid)>0) l=mid+eps;
    else r=mid-eps;
}

三分模板：

double l=0,r=1000;
while(l<=r){
    double mid=(l+r)/2,midd=(mid+r)/2;
    if(f(mid)>f(midd)) l=mid+eps;
    else r=mid-eps;
}

另外值得一提的是，如果了l , r为int型，可以mid = ( l + r) >> 1，更优化

思路:

这题的内容基本在图上了，就是先三分线段AB得到点E的坐标，然后每次得到点E就三分线段CD得到点F，最后便可求出最短时间

代码：

#include<bits/stdc++.h>
using namespace std;
double xa,xb,xc,xd,ya,yb,yc,yd,P,Q,R;
double f(double x1,double y1,double x2,double y2)
{
    double l1=sqrt((xa-x1)*(xa-x1)+(ya-y1)*(ya-y1));
    double l2=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    double l3=sqrt((xd-x2)*(xd-x2)+(yd-y2)*(yd-y2));
    return l1/P+l3/Q+l2/R;
}
double hhh(double xx,double yy)
{
    double lx=xc,ly=yc,rx=xd,ry=yd;
        while(abs(lx-rx)>1e-5||abs(ly-ry)>1e-5){
            double m1=(lx+rx)/2,mx=(rx+m1)/2,m2=(ly+ry)/2,my=(m2+ry)/2;
            double t1=f(xx,yy,m1,m2),t2=f(xx,yy,mx,my);
            if(t1>t2) {lx=m1; ly=m2;}
            else {rx=mx; ry=my;}
        }
    return min(f(xx,yy,lx,ly),f(xx,yy,rx,ry));
}
int main()
{
    while(cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd>>P>>Q>>R){
        double lx=xa,ly=ya,rx=xb,ry=yb;
        while(abs(lx-rx)>1e-5||abs(ly-ry)>1e-5){
            double m1=(lx+rx)/2,mx=(rx+m1)/2,m2=(ly+ry)/2,my=(m2+ry)/2;
            if(hhh(m1,m2)>hhh(mx,my)) {lx=m1; ly=m2;}
            else {rx=mx; ry=my;}
        }
        printf("%.2f\n",min(hhh(lx,ly),hhh(rx,ry)));
    }
}