Line belt

三分嵌套

#include<bits/stdc++.h>
#define eps 1E-10
using namespace std;  
struct node
{
  double x,y;
} p1,p2,p3,p4;
int p,q,r;
double dist(node a,node b,int speed)
{
  return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y))/speed;     //用勾股定理求斜边，线段/速度=时间
}

double solve(node Q)
{
  node low=p3,high=p4;                    //low=C ，hogh=D
  node mid,midmid;                        //中间值，嵌套中间值
  double sum1=-1,sum2=0;                  //精确到（eps）位就跳出循环

  while(fabs(sum2-sum1)>eps)              //绝对值的比较，因为他不是单调的。
  {

    mid.x=(low.x+high.x)/2;               //mid找到CD线段的中点
    mid.y=(low.y+high.y)/2;
    midmid.x=(high.x+mid.x)/2;            //midmid定位D点和mid的中点
    midmid.y=(high.y+mid.y)/2;

    sum1=dist(Q,mid,r)+dist(mid,p4,q);    //确定走完Z和Y所花的时间G(Y) = Z / R + Y / Q（局部变量）
  //cout<<dist(Q,mid,r)<<endl;
  //cout<<dist(mid,p4,q)<<endl;
    sum2=dist(Q,midmid,r)+dist(p4,midmid,q); 
  //cout<<mid.x<<" "<<mid.y<<endl;
  //cout<<midmid.x<<" "<<midmid.y<<endl;
  //cout<<sum1<<" "<<sum2<<endl;

    if(sum1<sum2)                         //更新三分的右端点
      high=midmid;
    else
      low=mid;
  }
  return dist(Q,mid,r)+dist(mid,p4,q); 
}
int main()
{
  int T;
  scanf("%d",&T);
  {
    while(T--)
    {
      scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
      scanf("%lf%lf%lf%lf",&p3.x,&p3.y,&p4.x,&p4.y);
      scanf("%d%d%d",&p,&q,&r);

      node low=p1,high=p2,mid,midmid;     //low=A ，high=B ，中间值，嵌套中间值
      double sum1=-1.0,sum2=0;            //定义两个中间值

      while(fabs(sum2-sum1)>eps)          //精确到（eps）位就跳出循环
      {
        mid.x=(low.x+high.x)/2;           //mid找到AB线段的中点
        mid.y=(low.y+high.y)/2;
        midmid.x=(high.x+mid.x)/2;        //midmid定位B点和mid的中点
        midmid.y=(high.y+mid.y)/2;

        sum1=dist(p1,mid,p)+solve(mid);   //确定在AB线段上花的时间F(X) = X / P（局部变量）
        sum2=dist(p1,midmid,p)+solve(midmid);

        if(sum1<sum2)                     //更新三分的右端点
          high=midmid;
        else
          low=mid;
      }
    //cout<<sum1;
      printf("%.2lf\n",sum1);
    }
  }
  return 0;
}

笔记：两个端点肯定是直线距离最短，先确定下AB线段的mid点，再三分CD线段的mid点，直到三分到小于eps后，又将外层的AB线段三分一次，又又重新三分CD线段，直到三分到题目要求的精度