【BZOJ-1857】传送带三分套三分

2021-11-12 00:19:30

1857: [Scoi2010]传送带

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1077 Solved: 575
[Submit][Status][Discuss]

Description

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

Input

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By 第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy 第三行是3个整数，分别是P，Q，R

Output

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

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

HINT

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10

Source

Day2

Solution

三分法,用于求单峰函数的极值问题,思路很好想

给定左右端点L,R;找出两个三等分点M1,M2(L<=M1<=M2<=R),如果M1比M2更优,则L=M1,否则R=M2

这道题,首先,关系很好找,发现是单峰函数,那么三分找最值即可

不过这里的话用到三分套三分,也非常好理解

对于外层三分出的M1,M2,如果比较大小,需要内部再进行三分来确定,这就是三分套三分

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define eps 1e-3

int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,P,Q,R;

double dist(double x1,double y1,double x2,double y2)

{

    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));

}

double Calc(double X,double Y)

{

    double Lx=Cx,Ly=Cy,Rx=Dx,Ry=Dy;

    while (fabs(Rx-Lx)>eps || fabs(Ry-Ly)>eps)

        {

            double Mx1=Lx+(Rx-Lx)/,My1=Ly+(Ry-Ly)/,Mx2=Lx+(Rx-Lx)/*,My2=Ly+(Ry-Ly)/*;

            double LL=dist(Ax,Ay,X,Y)/P+dist(X,Y,Mx1,My1)/R+dist(Mx1,My1,Dx,Dy)/Q;

            double RR=dist(Ax,Ay,X,Y)/P+dist(X,Y,Mx2,My2)/R+dist(Mx2,My2,Dx,Dy)/Q;

            if (LL>RR) Lx=Mx1,Ly=My1;

                else Rx=Mx2,Ry=My2;

        }

    return dist(Ax,Ay,X,Y)/P+dist(X,Y,Lx,Ly)/R+dist(Lx,Ly,Dx,Dy)/Q;

}

int main()

{

    Ax=read(); Ay=read(); Bx=read(); By=read();

    Cx=read(); Cy=read(); Dx=read(); Dy=read();

    P=read(); Q=read(); R=read();

    double Lx=Ax,Ly=Ay,Rx=Bx,Ry=By;

    while (fabs(Rx-Lx)>eps || fabs(Ry-Ly)>eps)

        {

            double Mx1=Lx+(Rx-Lx)/,Mx2=Lx+(Rx-Lx)/*,My1=Ly+(Ry-Ly)/,My2=Ly+(Ry-Ly)/*;

            double LL=Calc(Mx1,My1),RR=Calc(Mx2,My2);

            if (LL>RR) Lx=Mx1,Ly=My1;

                else Rx=Mx2,Ry=My2;

        }

    printf("%.2lf\n",Calc(Lx,Ly));

    return ;

}

我会说因为变量重名WA了3发吗....A Sad Story...

码农公寓