直接复制以前写的代码,还带注释,真棒!
咳咳。
这道题,我们算从A到D点的最短距离,那么明显的,我们考虑三分。
我们先三分出从A点到AB中的某个点X,作为出发点,然后,再三分出从X到CD的某个点Y,再从Y直接到D,这样,我们就可以求出最小的值了。
我们来看看,我们这样三分是否完备。
我们走的最短路线一共有四种情况,即是否走两条传送带。
如果我们不走AB传送带,那么,其实就相当于一开始我们从A点走到A点,再开始走
不走CD传送带,也就是相当于直接从X走到D点(两点之间线段最短,且速度相同,所以不走CD传送带的话,直接走到D是最短的)
所以,我们发现,我们这样三分是完全可行的!做一遍就行了!
(代码看起来很长,但是大部分其实都是板子/重复的,具体看下函数这些就好了,基本有相应注释(以前的好习惯现在全丢了qwq))
由于doule具有精度问题,所以建议卡下精度
代码:
#include<cstdio>//三分大法无限好,脑壳痛的不得了~ @_@
#include<cmath>
using namespace std;//方法:三分选取从AB上的哪个点开始,到CD上的哪个点,然后再从那个点到D点
const double eps=1e-4;//锁精度~
double ax,ay,bx,by,cx,cy,dx,dy;
double P,Q,R;
double a1,a2,b1,b2;
inline void swap(double &x,double &y){
double c;
c=x,x=y,y=c;
}
inline double f(double x,double a,double b){//已知x以及两系数,求y
return a*x+b;
}
inline double far(double x,double y,double m,double n){//求两点之间的距离
return sqrt((x-m)*(x-m)+(y-n)*(y-n));
}
inline double fi(double x,double y,double a,double b){
double tim=far(x,y,a,b)/R;
tim+=far(x,y,dx,dy)/Q;
return tim;
}
inline double suan(double x,double y){
double tim=far(x,y,ax,ay)/P;//A到(x,y)的时间
double l,r,ans,L,R;
if(cx==dx){
l=cy,r=dy;
if(l>r){
swap(l,r);
}
while(r-l>=eps){
double lx=l+(r-l)/3,rx=r-(r-l)/3;
L=fi(cx,lx,x,y),R=fi(cx,rx,x,y);
if(L<=R){
ans=L;
r=rx;
continue;
}
ans=R;
l=lx;
}
return ans+tim;
}
l=cx,r=dx;
if(l>r){
swap(l,r);
}
while(r-l>=eps){//三分由(x,y)到CD上的某点
double lx=l+(r-l)/3,rx=r-(r-l)/3;
L=fi(lx,f(lx,a2,b2),x,y),R=fi(rx,f(rx,a2,b2),x,y);
if(L<=R){
ans=L;
r=rx;
continue;
}
ans=R;
l=lx;
}
return tim+ans;
}
int main(){
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
scanf("%lf%lf%lf",&P,&Q,&R);
if(ax!=bx){
a1=(ay-by)/(ax-bx);
b1=(ay-a1*ax);
}
if(cx!=dx){
a2=(cy-dy)/(cx-dx);
b2=(cy-a2*cx);
}
double l,r,ans,L,R;
if(ax==bx){
l=ay,r=by;
if(l>r){
swap(l,r);
}
while(l<=r){
double lx=l+(r-l)/3,rx=r-(r-l)/3;
L=suan(ax,lx),R=suan(ax,rx);
if(L<=R){
ans=L;
r=rx-eps;
continue;
}
ans=R;
l=lx+eps;
}
printf("%.2lf",ans);
return 0;
}
l=ax,r=bx;
if(l>r){
swap(l,r);
}
while(r-l>=eps){//三分由A到AB中的一点(不走AB即为从A到A)
double lx=l+(r-l)/3,rx=r-(r-l)/3;
L=suan(lx,f(lx,a1,b1)),R=suan(rx,f(rx,a1,b1));
if(L<=R){
r=rx;
ans=L;
continue;
}
l=lx;
ans=R;
}
printf("%.2lf",ans);
return 0;
}
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/

京公网安备 11010502036488号