[SCOI2010]传送带 三分法

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

[SCOI2010]传送带

LG传送门

三分法模板。

关于为什么可以三分，我选择感性理解，有人证明了，总之我是懒得证了。

假设路径是\(A \to E \to F \to 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;
}