传送带【NOIP2016提高A组模拟8.14】

在写前先说一声，这道题题解有很多，我看了一篇比较好的，在此推荐一篇。 （http://www.cnblogs.com/1-1-1-1/p/5705179.html）。 这也是我第一打三分套三分，真是艰辛-_-|||，一堆错误。

---

题目（bzoj1857）

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

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

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

数据范围： 对于30%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10 1<=P,Q,R<=5 对于100%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000 1<=P,Q,R<=10

---

剖解题目

题目很清楚了，不知所措。

---

思路

我们动手画一画，可以发现路径与两条线段与平面的一些关系。

---

解法

显然，最优的路径一定是在AB上走一段，在走到CD段上，再在CD段上走到D点，那么离开AB与到达CD的两个点就是关键，求出它们就是关键的步骤了。（这两个点可以与两条线段端点重合）。 这是就要许多经验了，像我第一次打三分套三分的根本就没想到- -|||。 二分显然不行，因为判断不了答案到底是在左边还是右边，所以我们就三分AB线段，AB上就会有左右两个端点l,r，如果l更优，那么答案就会在A~r之间，如果r更优，那么答案就会在l~B之间，如果l与r一样优，那答案就在l与r之间。 当我们确定了AB上的点E时，我们现在要确定CD上的点F，这条F是对EF+FD两条线段和有很大的影响，我们利用两条线段所在直线解析式一算会发现这两条线段和的值的函数图像是一个上凹（下凸）的二次函数图像，这时目的是求这二次函数图像的峰值。 求峰值的方法，经典的就是三分法，原理和上面的一样。 这就形成了一个三分套三分！ 当然，这里遇到了实数精度的问题，所以在三分时第三种结果基本不会出现，因为题目要求保留两位小数，那么如果l与r两种答案的差值小于 10−4 或 10−5 时，我们就视为这两种答案是一样的。 然后精度是问题，别人程序优美 10−3 都过了，我的却要 10−5 ！坑了我正确率！

---

代码

#include<cstdio> #include<algorithm> #include<cstdlib> #include<cmath> #define Exp 1e-5 using namespace std; double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,P,Q,R; double dis(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double get(double x,double y) { double lx=Cx,ly=Cy,rx=Dx,ry=Dy,lxx,lyy,rxx,ryy; while (abs(rx-lx)>Exp || abs(ry-ly)>Exp) { lxx=lx+(rx-lx)/3; lyy=ly+(ry-ly)/3; rxx=lx+(rx-lx)/3*2; ryy=ly+(ry-ly)/3*2; double dl=dis(lxx,lyy,Dx,Dy)/Q,dr=dis(rxx,ryy,Dx,Dy)/Q; double nl=dis(x,y,lxx,lyy)/R,nr=dis(x,y,rxx,ryy)/R; dl+=nl; dr+=nr; if (abs(dl-dr)<Exp){ rx=rxx; ry=ryy; lx=lxx; ly=lyy; } else if (dl<dr) rx=rxx,ry=ryy; else lx=lxx,ly=lyy; } return dis(x,y,lx,ly)/R+dis(lx,ly,Dx,Dy)/Q; } 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); double lx=Ax,ly=Ay,rx=Bx,ry=By,lxx,lyy,rxx,ryy,ans=10000000; while (abs(rx-lx)>Exp || abs(ry-ly)>Exp) { lxx=lx+(rx-lx)/3; lyy=ly+(ry-ly)/3; rxx=lx+(rx-lx)/3*2; ryy=ly+(ry-ly)/3*2; double dl=dis(Ax,Ay,lxx,lyy)/P,dr=dis(Ax,Ay,rxx,ryy)/P; double nl=get(lxx,lyy),nr=get(rxx,ryy); dl=dl+nl; dr=dr+nr; if (abs(dl-dr)<Exp){ rx=rxx; ry=ryy; lx=lxx; ly=lyy; if (dl<ans) ans=dl; } else if (dl<dr) rx=rxx,ry=ryy; else lx=lxx,ly=lyy; } printf("%.2lf",ans); }