传送带

https://loj.ac/problem/10017

题目描述

  给出两条线段(AB)，(CD)，并且给出在线段(AB)，线段(CD)，平面上的移动速度，求从(A)点到(B)点最短的移动时间。

思路

  首先比较容易想到最优的移动路径一定由(A)到(AB)上一点(P)，(P)到(CD)上一点(Q)，(Q)到(D)的路径组成。这道题显然应该用三分做，二分是无法过的，因为我们无法保证这个题只是单调增或单调减。但(P)和(Q)都需要三分，我们就需要三分套三分。如果三分(P、Q)的横纵坐标，我们会发现代码比较复杂，所以我们可以三分(AQ)和(AB)的比值，以及三分(CQ)和(CD)的比值，这样可以发现码量大大减少了。

代码

#include <bits/stdc++.h>
using namespace std;
double ax,bx,cx,dx,ay,by,cy,dy,p,q,r;
double f(double a,double b,double c,double d)
{
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
double check2(double k1,double k2)
{
    double x1=ax+k1*(bx-ax),y1=ay+k1*(by-ay);
    double x2=cx+k2*(dx-cx),y2=cy+k2*(dy-cy);
    return f(ax,ay,x1,y1)/p+f(x1,y1,x2,y2)/r+f(x2,y2,dx,dy)/q;
}
double check(double k)
{
    double l=0,r=1,eps=1e-5;
    while(r-l>eps)
    {
        double lmid=l+(r-l)/3;
        double rmid=r-(r-l)/3;
        if(check2(k,lmid)<=check2(k,rmid))r=rmid;
        else l=lmid;
    }
    return check2(k,r);
}
int main() 
{
    scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
    scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
    scanf("%lf%lf%lf",&p,&q,&r);
    double l=0,r=1,eps=1e-5;
    while(r-l>eps)
    {
        double lmid=l+(r-l)/3;
        double rmid=r-(r-l)/3;
        if(check(lmid)<=check(rmid))r=rmid;
        else l=lmid;
    }
    printf("%.2lf",check(r));
    return 0;
}