题目链接
题解
画画图就发现实际上是在\(AB\)上和\(CD\)上分别选两个点\(E\),\(F\)，使得\(t_{AE} + t_{EF} + t_{FD}\)最小
然后猜想到当\(E\)固定时，这个值的函数关于\(|CF|\)是下凸的
当\(F\)总取最优时，关于\(|AE|\)也是下凸的
感觉十分的对
两层三分即可
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
struct point{
double x,y;
}A,B,C,D,AB,CD;
inline point operator -(const point& a,const point& b){
return (point){a.x - b.x,a.y - b.y};
}
inline point operator +(const point& a,const point& b){
return (point){a.x + b.x,a.y + b.y};
}
inline point operator *(const double& a,const point& b){
return (point){a * b.x,a * b.y};
}
double dis(const point& a,const point& b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double P,Q,R;
double cal2(double lam1,double lam2){
point E = A + lam1 * AB,F = C + lam2 * CD;
return dis(A,E) / P + dis(E,F) / R + dis(F,D) / Q;
}
double cal(double lam){
double l = 0,r = 1,lmid,rmid,len,cl,cr;
while (r - l > 0.00001){
len = r - l;
lmid = l + len / 3;
rmid = r - len / 3;
cl = cal2(lam,lmid); cr = cal2(lam,rmid);
if (cl > cr) l = lmid;
else r = rmid;
}
return cal2(lam,(r + l) / 2);
}
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);
AB = B - A; CD = D - C;
double l = 0,r = 1,lmid,rmid,len,cl,cr;
while (r - l > 0.00001){
len = r - l;
lmid = l + len / 3;
rmid = r - len / 3;
cl = cal(lmid); cr = cal(rmid);
if (cl > cr) l = lmid;
else r = rmid;
}
printf("%.2lf\n",cal((l + r) / 2));
return 0;
}