题意:二维平面上有两条线段,在$AB$上的移动速度为$p$,在$CD$上的移动速度为$q$,在平面上的移动速度$v$。现在从$A$点走到$D$点,最少需要多长时间
------------
要不是loli考三分我还真不知道三分的用处是啥qwq
其实就是用来求单峰函数的极值
对于这道题,ta的路径显然是先在$AB$上走到一点$E$,然后在平面上走到$CD$上一点$F$,再从$F$走到$D$
那么答案就是$|AE|/p+|EF|/v+|FD|/q$
这是一个二元函数,不方便直接求解
那就固定一个值,把它变成一个一元函数
固定一个参数$E$,记$f(E)=|EF|/v+|FD|/q$
画图可以发现它是一个单峰函数
答案为$Ans=|AE|/p+f(E)$,这又是一个单峰函数
所以这题正解就是三分套三分了qwq
把$eps$尽量设小一点,防止卡精度
```
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double db;
const db eps=1e-8,inf=1e9;
db ax,ay,bx,by,cx,cy,dx,dy,p,q,v;
db getdis(db x,db y,db xx,db yy){return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));}
db F(db x,db y,db xx,db yy){return getdis(x,y,xx,yy)/v+getdis(xx,yy,dx,dy)/q;}
db calc1(db x,db y)
{
db lx=cx,ly=cy,rx=dx,ry=dy;
while (getdis(lx,ly,rx,ry)>=eps)
{
db tmpx=(rx-lx)/3.0,tmpy=(ry-ly)/3.0;
db lmidx=lx+tmpx,rmidx=rx-tmpx;
db lmidy=ly+tmpy,rmidy=ry-tmpy;
db ans1=F(x,y,lmidx,lmidy),ans2=F(x,y,rmidx,rmidy);
if (ans2-ans1>=eps) rx=rmidx,ry=rmidy;
else lx=lmidx,ly=lmidy;
}
return F(x,y,lx,ly);
}
db calc()
{
db lx=ax,ly=ay,rx=bx,ry=by;
while (getdis(lx,ly,rx,ry)>eps)
{
db tmpx=(rx-lx)/3.0,tmpy=(ry-ly)/3.0;
db lmidx=lx+tmpx,rmidx=rx-tmpx;
db lmidy=ly+tmpy,rmidy=ry-tmpy;
db ans1=calc1(lmidx,lmidy)+getdis(ax,ay,lmidx,lmidy)/p;
db ans2=calc1(rmidx,rmidy)+getdis(ax,ay,rmidx,rmidy)/p;
if (ans2-ans1>=eps) rx=rmidx,ry=rmidy;
else lx=lmidx,ly=lmidy;
}
return calc1(lx,ly)+getdis(ax,ay,lx,ly)/p;
}
int main()
{
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
scanf("%lf%lf%lf",&p,&q,&v);
printf("%.2lf\n",calc());
return 0;
}
```