首页 > 代码库 > BZOJ 1857 传送带 (三分套三分)

BZOJ 1857 传送带 (三分套三分)

2024-08-30 22:34:12   224人阅读

在一个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位。

显然是先从AB的某点E出发，然后经过平面到达CD的某点F，然后从F到达D。
我们假设已经确定了E，然后我们确定CD的F时，我们通过直觉感知到随着点F从C移动到D
时间关于位移的函数图像是一个先减少后增加的图形。
我们再来确定E，通过直觉，
时间关于位移的函数图像依然是一个先减少后增加的图形。
所以我们先三分E，再三分F，
我们用三分套三分解决了这个问题。

技术分享 
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <math.h>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define MAXN 250005
# define eps 1e-3
# define MAXM 1000005
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
typedef unsigned long long ULL;
int _MAX(int a, int b){return a>b?a:b;}
int _MIN(int a, int b){return a>b?b:a;}
int Scan() {
    int res=0, flag=0;
    char ch;
    if((ch=getchar())==‘-‘) flag=1;
    else if(ch>=‘0‘&&ch<=‘9‘) res=ch-‘0‘;
    while((ch=getchar())>=‘0‘&&ch<=‘9‘)  res=res*10+(ch-‘0‘);
    return flag?-res:res;
}
void Out(int a) {
    if(a<0) {putchar(‘-‘); a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+‘0‘);
}

double ax, ay, bx, by, cx, cy, dx, dy, p, q, r;

double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double cal(double x, double y)
{
    double ans=dis(ax,ay,x,y)/p;
    double lx=cx, ly=cy, rx=dx, ry=dy;
    while (dis(lx,ly,rx,ry)>eps) {
        double P1x=(lx+lx+rx)/3, P1y=(ly+ly+ry)/3, P2x=(lx+rx+rx)/3, P2y=(ly+ry+ry)/3;
        double t1=dis(P1x,P1y,dx,dy)/q+dis(x,y,P1x,P1y)/r, t2=dis(P2x,P2y,dx,dy)/q+dis(x,y,P2x,P2y)/r;
        if (t1<=t2) rx=P2x, ry=P2y;
        else lx=P1x, ly=P1y;
    }
    return ans+dis(lx,ly,dx,dy)/q+dis(x,y,lx,ly)/r;
}
int main ()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy,&p,&q,&r);
    double lx=ax, ly=ay, rx=bx, ry=by;
    while (dis(lx,ly,rx,ry)>eps) {
        double P1x=(lx+lx+rx)/3, P1y=(ly+ly+ry)/3, P2x=(lx+rx+rx)/3, P2y=(ly+ry+ry)/3;
        double t1=cal(P1x,P1y), t2=cal(P2x,P2y);
        if (t1<=t2) rx=P2x, ry=P2y;
        else lx=P1x, ly=P1y;
    }
    printf("%.2lf\n",cal(lx,ly));
    return 0;
}
View Code

 

BZOJ 1857 传送带 (三分套三分)


联系
我们