BZOJ 1857 [Scoi2010]传送带三分套三分

本文主要是介绍BZOJ 1857 [Scoi2010]传送带三分套三分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

传送门

简单yy证明一下，从A到D的路程一定是AB上一段，平面内一段，CD上一段的。

也就是说不存在“折返”的情况。

那么假设AB上从A连续走到了(x1,y1)，然后在CD上走到(x2,y2)后走到了D，

写一下距离的表达式，把距离分成3段（省去开根）：

(Ax,Ay)~(x1,y1)：(x1-Ax)^2+(y1-Ay)^2

(x1,y1)~(x2,y2)：(x1-x2)^2+(y1-y2)^2

(x2,y2)~(Dx,Dy)：(x2-Dx)^2+(y2-Dy)^2

时间就是距离除以上面的速度了，因为是常量，就不表示了。

假设我们枚举一下AB上的那个点(x1,y1)，那么未知量就是(x2,y2)了，

其它量都看做已知量，我们得到了一个二元式f(x,y)=ax^2+by^2+cx+dy+e

由于是在一条线段上的（woc一开始没看见死活不会……）

所以实际上y和x有一个一次关系，这个二元式实际上是一个二次函数……

也就是说……单峰！

发现x^2前面的系数是正的，所以是下凸的，，那么(x2,y2)就可以简单地三分出来了。

但是直接枚举(x1,y1)似乎太慢了，于是就去猜想是不是也可以三分。

事实上和上面那个是类似的……

可以考虑固定一个最优的(x2,y2)来看。

所以就是三分(x1,y1)，同时三分(x2,y2)了，所谓“三分套三分”

只要注意是个下凸的函数就好了其它也没什么。。

#include<bits/stdc++.h>
using namespace std;
const doubleeps=1e-4;
double P,Q,R,Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double Work_CD(double x,double y){double Lx=Cx,Ly=Cy,Rx=Dx,Ry=Dy;while (fabs(Lx-Rx)>eps || fabs(Ly-Ry)>eps){double lxmid=Lx+(Rx-Lx)/3.0,lymid=Ly+(Ry-Ly)/3.0,rxmid=Lx+(Rx-Lx)/3.0*2.0,rymid=Ly+(Ry-Ly)/3.0*2.0;if (dis(x,y,lxmid,lymid)/R+dis(Dx,Dy,lxmid,lymid)/Q>dis(x,y,rxmid,rymid)/R+dis(Dx,Dy,rxmid,rymid)/Q)Lx=lxmid,Ly=lymid;elseRx=rxmid,Ry=rymid;}return dis(x,y,Lx,Ly)/R+dis(Dx,Dy,Lx,Ly)/Q;
}
double Work_AB(){double Lx=Ax,Ly=Ay,Rx=Bx,Ry=By;while (fabs(Lx-Rx)>eps || fabs(Ly-Ry)>eps){double lxmid=Lx+(Rx-Lx)/3.0,lymid=Ly+(Ry-Ly)/3.0,rxmid=Lx+(Rx-Lx)/3.0*2.0,rymid=Ly+(Ry-Ly)/3.0*2.0;if (dis(Ax,Ay,lxmid,lymid)/P+Work_CD(lxmid,lymid)>dis(Ax,Ay,rxmid,rymid)/P+Work_CD(rxmid,rymid))Lx=lxmid,Ly=lymid;elseRx=rxmid,Ry=rymid;}return dis(Ax,Ay,Lx,Ly)/P+Work_CD(Lx,Ly);
}
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);printf("%.2lf\n",Work_AB());return 0;
}

这篇关于BZOJ 1857 [Scoi2010]传送带三分套三分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！