Line belt

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5801    Accepted Submission(s): 2301

 

题意：给定A,B,C,D四个点，即：两线段AB和CD的端点，求从A到D的最短所用的时间。其中p，q，r分别为在AB,CD 以及其他地方的速度。

思路：因为两点之间直线段最短，所以至多分为三段，一段AB上的，一段CD上的，一段两线段之间的EF，而这三部分上的所用时间x,y,z与最终答案为下凸函数，所以这里用三分求极值 ，先三分出AB上的E点，然后三分CD上的F点，然后计算三部分的和即可。

三分思路：https://blog.csdn.net/deletewo/article/details/104102359

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const double eps=1e-6;

struct point{
    double x,y;
};
point A,B,C,D,E,F;

int t,p,q,R;

double dis(point a,point b){return sqrt(eps+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

double f(double t)
{
    F.x=D.x+(C.x-D.x)/dis(C,D)*q*t;
    F.y=D.y+(C.y-D.y)/dis(C,D)*q*t;
    return t+dis(E,F)/R;
}

double cal(double t)
{
    E.x=A.x+(B.x-A.x)/dis(A,B)*p*t;//(B.x-A.x)/dis(A,B)相当于cos*AB上移动的距离，得出x上的分量
    E.y=A.x+(B.y-A.y)/dis(A,B)*p*t;//同理，同上
    double l=0,r=dis(C,D)/q;
    while(r-l>eps){
        double m1=l+(r-l)/3;
        double m2=r-(r-l)/3;
        if(f(m1)>f(m2)+eps) l=m1;
        else r=m2;
    }
    return t+f(l);
}

signed main()
{
    cin>>t;
    while(t--){
          cin>>A.x>>A.y>>B.x>>B.y;
          cin>>C.x>>C.y>>D.x>>D.y;
          cin>>p>>q>>R;
          double l=0,r=dis(A,B)/p;
          while(r-l>eps){
                double m1=l+(r-l)/3;
                double m2=r-(r-l)/3;
                if(cal(m1)>cal(m2)+eps) l=m1;//两个三分点，这里取最小值，把较大的三分点作为下一次的边界
                else r=m2;
          }
          printf("%.2f\n",cal(l));
    }
    return 0;
}