[SCOI2010]传送带[三分]-LMLPHP

//point(AB)->point(CD) 距离满足下凸性,用三分套三分实现
#include<cmath>
#include<cstdio>
#include<iostream>
#define pf(x) ((x)*(x))
using namespace std;
typedef double real;
const real eps=1e-;
real ax,ay,bx,by,cx,cy,dx,dy,P,Q,R,ans;
inline real dis(real x1,real y1,real x2,real y2){
return sqrt(pf(x1-x2)+pf(y1-y2));
}
inline real trichotomy2_(real x,real y){//CD无斜率
real l,r,lmid,rmid,t1,t2;
l=min(cy,dy);r=max(cy,dy);
while(l+eps<r){
lmid=(l*+r)/,rmid=(l+r*)/;
t1=dis(cx,lmid,x,y)/R+dis(cx,lmid,dx,dy)/Q;
t2=dis(cx,rmid,x,y)/R+dis(cx,rmid,dx,dy)/Q;
if(t1<t2) r=rmid;
else l=lmid;
}
t1=dis(cx,l,x,y)/R+dis(cx,l,dx,dy)/Q;
return t1;
}
inline real trichotomy2(real x,real y){//CD有斜率
if(cx==dx) return trichotomy2_(x,y);
real l,r,lmid,rmid,k,b,t1,t2;
l=min(cx,dx);r=max(cx,dx);
k=(cy-dy)/(cx-dx);
b=cy-k*cx;
while(l+eps<r){
lmid=(l*+r)/,rmid=(l+r*)/;
t1=dis(lmid,k*lmid+b,x,y)/R+dis(lmid,k*lmid+b,dx,dy)/Q;
t2=dis(rmid,k*rmid+b,x,y)/R+dis(rmid,k*rmid+b,dx,dy)/Q;
if(t1<t2) r=rmid;
else l=lmid;
}
t1=dis(l,k*l+b,x,y)/R+dis(l,k*l+b,dx,dy)/Q;
return t1;
}
inline real trichotomy1(){//AB有斜率
real l,r,lmid,rmid,k,b,t1,t2;
l=min(ax,bx);r=max(ax,bx);
k=(ay-by)/(ax-bx);
b=ay-k*ax;
while(l+eps<r){
lmid=(l*+r)/,rmid=(l+r*)/;
t1=trichotomy2(lmid,k*lmid+b)+dis(lmid,k*lmid+b,ax,ay)/P;
t2=trichotomy2(rmid,k*rmid+b)+dis(rmid,k*rmid+b,ax,ay)/P;
if(t1<t2) r=rmid;
else l=lmid;
}
t1=trichotomy2(l,k*l+b)+dis(l,k*l+b,ax,ay)/P;
ans=min(ans,t1);
}
inline real trichotomy1_(){//AB无斜率
real l,r,lmid,rmid,t1,t2;
l=min(ay,by);r=max(ay,by);
while(l+eps<r){
lmid=(l*+r)/,rmid=(l+r*)/;
t1=trichotomy2(ax,lmid)+dis(ax,lmid,ax,ay)/P;
t2=trichotomy2(ax,rmid)+dis(ax,rmid,ax,ay)/P;
if(t1<t2) r=rmid;
else l=lmid;
}
t1=trichotomy2(ax,l)+dis(ax,l,ax,ay)/P;
ans=min(ans,t1);
}
int main(){
cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy;
cin>>P>>Q>>R;
ans=dis(ax,ay,dx,dy);
if(ax!=bx) trichotomy1();
else trichotomy1_();
printf("%.2lf",ans);
return ;
}
05-11 20:41