P2571 [SCOI2010]传送带 三分

题意：

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

范围&性质： 1 ≤ a x , a y , b x , b y , c x , c y , d x , d y ≤ 1 0 3 , 1 ≤ p , q , r ≤ 10 1\le a_x,a_y,b_x,b_y,c_x,c_y,d_x,d_y \le 10^3,1\le p,q,r\le 10 1≤ax​,ay​,bx​,by​,cx​,cy​,dx​,dy​≤103,1≤p,q,r≤10

分析：

题目相当于在$AB,CD$上分别求出一个点$E，F$,使得 d i s ( A , E ) p + d i s ( E , F ) r + d i s ( F , d ) q \frac{dis(A,E)}{p}+\frac{dis(E,F)}{r}+\frac{dis(F,d)}{q} pdis(A,E)​+rdis(E,F)​+qdis(F,d)​最小，我们画图可以发现，当$E$固定时，$F$的取值是一个单峰函数，所以我们可以三分，整体就是三分套三分

代码：

#includeusing namespace std;namespace zzc
{const double eps = 1e-6;double p,q,r;double ax,ay,bx,by,cx,cy,dx,dy;double dis(double x1,double y1,double x2,double y2){return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double tridiv2(double ex,double ey){double lx=cx,ly=cy,rx=dx,ry=dy;while(dis(lx,ly,rx,ry)>=eps){double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;double lmidx=lx+tmpx,lmidy=ly+tmpy;double rmidx=rx-tmpx,rmidy=ry-tmpy;double lans=dis(ex,ey,lmidx,lmidy)/r+dis(dx,dy,lmidx,lmidy)/q;double rans=dis(ex,ey,rmidx,rmidy)/r+dis(dx,dy,rmidx,rmidy)/q;if(rans-lans>eps) rx=rmidx,ry=rmidy;else lx=lmidx,ly=lmidy;}return dis(ex,ey,lx,ly)/r+dis(dx,dy,lx,ly)/q;;}double tridiv1(){double lx=ax,ly=ay,rx=bx,ry=by;while(dis(lx,ly,rx,ry)>=eps){double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;double lmidx=lx+tmpx,lmidy=ly+tmpy;double rmidx=rx-tmpx,rmidy=ry-tmpy;double lans=tridiv2(lmidx,lmidy)+dis(ax,ay,lmidx,lmidy)/p;double rans=tridiv2(rmidx,rmidy)+dis(ax,ay,rmidx,rmidy)/p;if(rans-lans>eps) rx=rmidx,ry=rmidy;else lx=lmidx,ly=lmidy;}return tridiv2(lx,ly)+dis(ax,ay,lx,ly)/p;}void work(){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",tridiv1());}}int main()
{zzc::work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！