首页 > 代码库 > bzoj 1857: [Scoi2010]传送带 三分
bzoj 1857: [Scoi2010]传送带 三分
三分:
单峰函数求最值，设$mid1=l+(r-l)/3$,$mid2=l+2*(r-l)/3$。
假设是一个上凸的函数,当$f(mid1)<f(mid2)$,$mid1$左侧不可能有最值。
否则$mid2$右侧不可能有最值。
这道题如果固定住一个点那另一个点的位置与时间关系是一个单峰函数，具体可以用求导找零点证。
那就推测选的第一个点的函数也是单峰的，直接三分套三分就好了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 double ax,ay,bx,by,cx,cy,dx,dy; 8 double p,q,r; 9 const double eps=1e-3;10 double dis(double x1,double y1,double x2,double y2)11 {12 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));13 }14 double a1,a2;15 double cal(double x,double y)16 {17 double lx=cx,ly=cy,rx=dx,ry=dy;18 double x1,y1,x2,y2,t1,t2;19 while(fabs(rx-lx)>eps||fabs(ry-ly)>eps)20 {21 x1=lx+(rx-lx)/3;y1=ly+(ry-ly)/3;22 x2=lx+(rx-lx)/3*2;y2=ly+(ry-ly)/3*2;23 t1=dis(a1,a2,x,y)/p+dis(x1,y1,x,y)/r+dis(x1,y1,dx,dy)/q;24 t2=dis(a1,a2,x,y)/p+dis(x2,y2,x,y)/r+dis(x2,y2,dx,dy)/q;25 if(t1>t2)26 {27 lx=x1;ly=y1;28 }29 else30 {31 rx=x2;ry=y2;32 }33 }34 return dis(a1,a2,x,y)/p+dis(lx,ly,x,y)/r+dis(lx,ly,dx,dy)/q;35 }36 int main()37 {38 scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy,&p,&q,&r);39 double x1,y1,x2,y2,t1,t2;40 a1=ax;a2=ay;41 while(fabs(bx-ax)>eps||fabs(by-ay)>eps)42 {43 x1=ax+(bx-ax)/3;y1=ay+(by-ay)/3;44 x2=ax+(bx-ax)/3*2;y2=ay+(by-ay)/3*2;45 t1=cal(x1,y1);t2=cal(x2,y2);46 if(t1>t2)47 {48 ax=x1;ay=y1;49 }50 else51 {52 bx=x2;by=y2;53 }54 }55 printf("%.2lf\n",cal(ax,ay));56 return 0;57 }
bzoj 1857: [Scoi2010]传送带 三分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。