bzoj1857传送带—

bzoj1857传送带——三分法

本文主要是介绍bzoj1857传送带——三分法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

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

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

0 0 0 100
100 0 100 100
2 2 1
Sample Output

136.60
HINT

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10

我们先假设我们在AB上已经选定了一个定点x，那么剩下的任务就是在CD上选一点y，使得AxyD最短，非常显然，再CD上选一个y绝对是一个单峰函数。于是我们可以用三分法求出这个函数的最小值，也就是说对于每一个x，我们可以求出y点。那么我们怎么着x使得y最优呢？

可以证明，x也是一个单峰函数(网上有证明，然而我并不是特别会证)，于是我们可以用三分求出x的最优值，所以我们可以三分套三分，先三分一层x，然后再三分y求最优值即可。

#include<bits/stdc++.h>
#define db double
#define eps 1e-8
using namespace std;
int read(){char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
} 
int ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
db lx,rx,ly,ry,lxm,rxm,lym,rym,t1,t2;
db dis(db x1,db y1,db x2,db y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
db calc(db x,db y){db lx=cx,ly=cy,rx=dx,ry=dy;db lxm,lym,rxm,rym,t1,t2;while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){lxm=lx+(rx-lx)/3;lym=ly+(ry-ly)/3;rxm=rx+(lx-rx)/3;rym=ry+(ly-ry)/3;t1=dis(ax,ay,x,y)/p+dis(x,y,lxm,lym)/r+dis(lxm,lym,dx,dy)/q;t2=dis(ax,ay,x,y)/p+dis(x,y,rxm,rym)/r+dis(rxm,rym,dx,dy)/q;if(t1>t2) lx=lxm,ly=lym;else rx=rxm,ry=rym;}return dis(ax,ay,x,y)/p+dis(x,y,lx,ly)/r+dis(lx,ly,dx,dy)/q;
}
int main()
{ax=read();ay=read();bx=read();by=read();cx=read();cy=read();dx=read();dy=read();p=read();q=read();r=read();lx=ax;ly=ay;rx=bx;ry=by;while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){lxm=lx+(rx-lx)/3;lym=ly+(ry-ly)/3;rxm=rx+(lx-rx)/3;rym=ry+(ly-ry)/3;t1=calc(lxm,lym);t2=calc(rxm,rym);if(t1>t2) lx=lxm,ly=lym;else rx=rxm,ry=rym;}printf("%.2lf",calc(lx,ly));return 0;
}