[SCOI2010]传送带
三分法模板。
关于为什么可以三分,我选择感性理解,有人证明了,总之我是懒得证了。
假设路径是(A o E o F o D),(E)和(F)分别是从(AB)到平面上的拐角和从平面上到(CD)上的拐角。首先三分(E)的位置,在此基础上三分(F)的位置就可以了。
#include<cstdio>
#include<cmath>
#define I inline
#define D double
using namespace std;
const D eps=1e-6;
struct N{D x,y;}a,b,c,d;
D P,Q,R;
I D pwr(D x){return x*x;}
I D dst(N a,N b){return sqrt(pwr(a.x-b.x)+pwr(a.y-b.y));}
D dac0(N f){
N l=c,r=d,p,q;
D u,v,o,e;
while(dst(l,r)>eps)
u=(r.x-l.x)/3,v=(r.y-l.y)/3,p=(N){l.x+u,l.y+v},q=(N){r.x-u,r.y-v},o=dst(f,p)/R+dst(p,d)/Q,e=dst(f,q)/R+dst(q,d)/Q,e-o>eps?r=q:l=p;
return dst(f,l)/R+dst(l,d)/Q;
}
D dac(){
N l=a,r=b,p,q;
D u,v,o,e;
while(dst(l,r)>eps)
u=(r.x-l.x)/3,v=(r.y-l.y)/3,p=(N){l.x+u,l.y+v},q=(N){r.x-u,r.y-v},o=dst(a,p)/P+dac0(p),e=dst(a,q)/P+dac0(q),e-o>eps?r=q:l=p;
return dac0(l)+dst(a,l)/P;
}
int main(){
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&P,&Q,&R);
printf("%.2lf",dac());
return 0;
}