三分套三分模板
貌似只要是单峰函数就可以用三分求解
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #define eps 1e-9 using namespace std; struct node{ double x,y; }a,b,c,d; double p,q,r; inline node get(node a, node b, double p){ node ans; ans.x=a.x+(b.x-a.x)*p; ans.y=a.y+(b.y-a.y)*p; return ans; } inline double dist(node x, node y){ return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)); } inline double calc(node x, node y){ return dist(a,x)/p+dist(x,y)/r+dist(y,d)/q; } inline double solve(node t){ double l=0.0,r=1.0,ans; while (fabs(l-r)>eps){ , m2=m1+(r-l)*; node x=get(c,d,m1), y=get(c,d,m2); if (calc(t,x)<calc(t,y)) ans=m1,r=m2; else ans=m2, l=m1; } node x=get(c,d,ans); return calc(t,x); } int main(){ scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y); scanf("%lf%lf%lf%lf", &c.x, &c.y, &d.x, &d.y); scanf("%lf%lf%lf", &p, &q, &r); double l=0.0,r=1.0,ans; while (fabs(l-r)>eps){ , m2=m1+(r-l)*; node x=get(a,b,m1), y=get(a,b,m2); if (solve(x)<solve(y)) ans=m1,r=m2; else ans=m2,l=m1; } node x=get(a,b,ans); printf("%.2lf\n", solve(x)); ; }