一道很适合练习三分的题目三分套三分强不强
题意：给你平面上两条平行线段\(AB\)和\(CD\)，一个人要从\(A\)走到\(D\)，他在线段\(AB\)上的速度为\(P\)，在\(CD\)上的速度为\(Q\)，在其他地方的速度为\(R\)。求从\(A\)到\(D\)的最短时间。
这题目我想在许多初中数学题中经常可以看见。我们只需要在\(AB\)上取一点\(E\)，在\(CD\)上取一点\(F\)，然后按\(A\to E\ E\to F\ F\to D\)的 顺序即可算出时间。
我们先考虑已知\(E\)的位置，如何确定\(F\)？
这个还是很好想的，\(F\)肯定在一个位置时可以保证\(E\to F\ F\to D\)的时间最短。这个证明都不用吧
然后这就是一个凹性函数，我们有发现\(E\)的移动过程中\(A\to E\)是一个正比例函数，然后两条函数一重合——就还是一个凹性函数
然后我们对于\(E\)的位置也可以三分求解。这样我们三分套三分即可解决。
但是这一注意有一个坑点：所给的线段不一定平行于\(x\)轴或\(y\)轴。所以我们要三分比例
这个具体还是看CODE的做法吧
#include<cstdio>
#include<cmath>
using namespace std;
typedef double DB;
const DB EPS=1e-6;
struct point
{
DB x,y;
}A,B,C,D;
int P,Q,R,T;
inline DB dis(point A,point B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
inline DB calc(DB p1,DB p2)
{
point X,Y;
X.x=p1*(B.x-A.x)+A.x; X.y=p1*(B.y-A.y)+A.y;
Y.x=p2*(D.x-C.x)+C.x; Y.y=p2*(D.y-C.y)+C.y;
return dis(A,X)/P+dis(X,Y)/R+dis(Y,D)/Q;
}
inline DB get(DB p1)
{
DB l=0,r=1.0;
while (r-l>EPS)
{
DB lmid=l+(r-l)/3.0,rmid=r-(r-l)/3.0;
if (calc(p1,lmid)<=calc(p1,rmid)) r=rmid; else l=lmid;
}
return calc(p1,l);
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);
scanf("%d%d%d",&P,&Q,&R);
DB l=0,r=1.0;
while (r-l>EPS)
{
DB lmid=l+(r-l)/3.0,rmid=r-(r-l)/3.0;
if (get(lmid)<=get(rmid)) r=rmid; else l=lmid;
}
printf("%.2lf\n",get(l));
}
return 0;
}