洛谷P2571.传送带

洛谷P2571.传送带

• 三分模板题

• 用于单峰函数求极值

  • 一定可以将答案路径分成三段
  • 即AE - EF - FD (E和A可能重复，F和D可能重合)
    • E在线段AB上，F在线段CD上
  • 因为有两个不定点EF，因此假设E为参数，三分求F的位置
  • 再外层三分求E的位置
  • 

•   #include<iostream>#include<cmath>#include<cstdio>#include<cstring>using namespace std;const double eps=1e-8;double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;double dis(double x1,double y1,double x2,double y2){double x_dis = x2 - x1 ,y_dis = y2 - y1;return sqrt(x_dis*x_dis + y_dis*y_dis);}//上图中f函数 用于三分找Fdouble f(double x1,double y1,double x2,double y2){return dis(x1,y1,x2,y2)/r + dis(x2,y2,dx,dy)/q;}double calc1(double x,double y)  //同理三分{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,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy;double ans1=f(x,y,lmidx,lmidy),ans2=f(x,y,rmidx,rmidy);if(ans2 - ans1 > eps) rx = rmidx,ry = rmidy;else lx = lmidx,ly = lmidy;}return f(x,y,lx,ly);}double calc(){//三分double lx=ax,ly=ay,rx=bx,ry=by;//两点不重合while(dis(lx,ly,rx,ry)>eps){//x和y的三等分间距double tmpx = (rx - lx) / 3,tmpy = (ry - ly) / 3;//左三等分点 和 右三等分点double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy;//左右两点各求一次答案double ans1=calc1(lmidx,lmidy) + dis(ax,ay,lmidx,lmidy)/p;double ans2=calc1(rmidx,rmidy) + dis(ax,ay,rmidx,rmidy)/p;//ans1更小，就是更优，往左收缩区间if(ans2 - ans1 > eps) rx = rmidx,ry = rmidy;else lx = lmidx,ly = lmidy;}return calc1(lx,ly) + dis(ax,ay,lx,ly)/p;}int main(){cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r;printf("%.2lf\n",calc());}