2021-10-05 二分三分算法 求解最小值 传送带（951G）

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段ABtext{AB}AB和线段CDtext{CD}CD。lxhgww在ABtext{AB}AB上的移动速度为P，在CDtext{CD}CD上的移动速度为Q，在平面上的移动速度R。
现在lxhgww想从A点走到D点，他想知道最少需要走多长时间。

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax,Ay,Bx,ByA_x,A_y,B_x,B_yAx​,Ay​,Bx​,By​；
第二行是4个整数，表示C和D的坐标，分别为Cx,Cy，Dx,DyC_x,C_y，D_x,D_yCx​,Cy​，Dx​,Dy​，；
第三行是3个整数，分别是P,Q,R。

输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位。

示例1

复制0 0 0 100 100 0 100 100 2 2 1

0 0 0 100
100 0 100 100
2 2 1

复制136.60

136.60

#include
#include
#include
#include
#include
using namespace std;
struct Node{
    double x,y;
}a,b,c,d;

double x1,ya,x2,y2,x3,y3,x4,y4;
double p,q,r;

double dis(double xx,double yy,double xxx,double yyy)
{
    return sqrt((xxx-xx)*(xxx-xx)+(yyy-yy)*(yyy-yy));
}

double min(double ex,double ey)
{
    double sum=(dis(x1,ya,ex,ey))/p;
    double midx,midy,mid2x,mid2y;
    
    
    for(int i=0;i<100;i++)
    {
        midx=(c.x+d.x)/2;
        midy=(c.y+d.y)/2;
        mid2x=(midx+d.x)/2;
        mid2y=(midy+d.y)/2;
        if(  dis(ex,ey,midx,midy)/r+dis(midx,midy,x4,y4)/q   >a.x>>a.y>>b.x>>b.y;
    cin>>c.x>>c.y>>d.x>>d.y;
    x1=a.x;
    ya=a.y;
    x2=b.x;
    y2=b.y;
    x3=c.x;
    y3=c.y;
    x4=d.x;
    y4=d.y;
    cin>>p>>q>>r;
    double midx,midy,mid2x,mid2y;
    for(int i=0;i<100;i++)
    {
        midx=(a.x+b.x)/2;
        midy=(a.y+b.y)/2;
        mid2x=(midx+b.x)/2;
        mid2y=(midy+b.y)/2;
        if(    min(midx,midy)< min(mid2x,mid2y))
        {
            b.x=mid2x;
            b.y=mid2y;
        }
        else
        {
            a.x=midx;
            a.y=midy;
        }
    }
   
     printf("%.2fn",min(a.x,a.y));
    return 0;
    
}

1.二分三分算法：

最常见的二分算法是折半查找，作用：求解一个单调函数的零点；

作用：求解一个在一个区间内凹凸函数的极大（小）值

用途：求有俩个变量的函数的最大或最小的（传送带即为这样的问题），假设一个变量为定植求              最 大（小）值，再假设另一个值为定制，求最大（小）问题，然后综合即为最大（小）值。

具体实现：

 三分算法也是一种暴力查找法，查找到无限趋近于最好的情况。

 其中main函数则为确定了F的位置求E变的最小值，min函数为E为定植，改变F的位置求最小值。

                                                                                                  一起敲代码，每日一分享（JN）