这是一道三分的模板题。

其实我瞥了一眼题解才发现是三分

至少学会了一个套路。

AC后看了看题解，5篇中就2篇是三分，结果一篇没有 $\LaTeX$ 真不爽，一篇就一点点代码……

不多说了，开始。

题目大意：

你要从 $A$ 点到 $D$ 点。有两条传送带：第一条从 $A$ 到 $B$，速度为 $p$，第二条从 $C$ 到 $D$，速度为 $q$。不走传送带时速度为 $r$。求从 $A$ 到 $D$ 的最少时间。

明显这条路径应该是三条线段组成的：$AE+EF+FD$。其中 $E$ 在 $AB$ 上，$F$ 在 $CD$ 上。

（以下设 $dis(X,Y)$ 为 $X$ 和 $Y$ 的距离）

那么答案就是 $dis(A,E)/p+dis(E,F)/r+dis(F,D)/q$。

这实际上是一个二元函数，想要求最小值还比较麻烦。

假设我们把其中一个元（这里取 $E$）当做参数会怎么样？

那么就是要找一点 $F$ 使得 $dis(E,F)/r+dis(F,D)/q$ 最小。

（以下设 $f(X)=(dis(X,F)/r+dis(F,D)/q)_{min}$）

容易发现这是个单峰或者单调函数。

有几何画板或者GeoGebra的自己试一下吧，我也说不太清楚……

反正就是 $f(E)$ 是可以通过三分 $F$ 得到最小值的。

但是其实 $E$ 也是个未知量啊！那怎么取得 $dis(A,E)/p+f(E)$ 的最小值呢？

我们发现这也是个单峰或单调函数。可以再三分 $E$ 得出这个最小值，也就是答案。

综上：这题就是三分套三分。

上代码：（详细注释）

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;	//我一般喜欢把eps设为1e-8，当然对于这题1e-6足够了
double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
double dis(double x_1,double y_1,double x_2,double y_2){	//P1和P2的距离
	double xdis=x_1-x_2,ydis=y_1-y_2;
	return sqrt(xdis*xdis+ydis*ydis);
}
double f(double x_1,double y_1,double x_2,double y_2){	//上文中提到的f(P1)在当F是P2时的值
	return dis(x_1,y_1,x_2,y_2)/r+dis(x_2,y_2,dx,dy)/q;
    //第一个是dis(E,F)/r，第二个是dis(F,D)/q
}
double calc1(double x,double y){	//内层三分F（这个给定的参数是固定E是这个点）
	double lx=cx,ly=cy,rx=dx,ry=dy;	//在CD上三分
	while(dis(lx,ly,rx,ry)>eps){	//还没有重合成一点
		double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;
		double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy;	//(lmidx,lmidy)是左等分点，(rmidx,rmidy)是右等分点
		double 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);	//返回这个最小值
}
double calc(){	//外层三分E
	double lx=ax,ly=ay,rx=bx,ry=by;	//在AB上三分
	while(dis(lx,ly,rx,ry)>eps){
		double tmpx=(rx-lx)/3,tmpy=(ry-ly)/3;
		double lmidx=lx+tmpx,rmidx=rx-tmpx,lmidy=ly+tmpy,rmidy=ry-tmpy;	//以上同理
		double ans1=calc1(lmidx,lmidy)+dis(ax,ay,lmidx,lmidy)/p,ans2=calc1(rmidx,rmidy)+dis(ax,ay,rmidx,rmidy)/p;	//左等分点和右等分点的值（在这里套了内层三分）
		if(ans2-ans1>eps) rx=rmidx,ry=rmidy;
		else lx=lmidx,ly=lmidy;	//同理
	}
	return calc1(lx,ly)+dis(ax,ay,lx,ly)/p;	//返回最小值，也就是答案
}
int main(){
	scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy,&p,&q,&r);
	printf("%.2lf\n",calc());	//这就是答案
}

表示蒟蒻并不会楼下的什么三分套三分退火啊粒子群啊……只能暴力了……

我是这样做的，把每一条线段平均拆成5000个点，然后两条线段上的点对之间两两匹配，取时间最小的

然后之后我交了一发三分竟然WA了

所以暴力才是最正确的方法

//minamoto
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
double x[N+5],y[N+5],xx[N+5],yy[N+5];
double t1[N+5],t2[N+5];
inline double dis(int i,int j){return sqrt((x[i]-xx[j])*(x[i]-xx[j])+(y[i]-yy[j])*(y[i]-yy[j]));}
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,p,q,r,ans=1e18;
int main(){
//	freopen("testdata.in","r",stdin);
//	freopen("transporter.in","r",stdin);
//	freopen("transporter.out","w",stdout);
    cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>p>>q>>r;
    double dx=(Bx-Ax)/N,dy=(By-Ay)/N;
    for(int i=0;i<=N;++i){
        x[i]=Ax+dx*i,y[i]=Ay+dy*i;
        t1[i]=sqrt(dx*i*dx*i+dy*i*dy*i)/p;
    }
    dx=(Dx-Cx)/N,dy=(Dy-Cy)/N;
    for(int i=0;i<=N;++i){
        xx[i]=Dx-dx*i,yy[i]=Dy-dy*i;
        t2[i]=sqrt(dx*i*dx*i+dy*i*dy*i)/q;
    }
    for(int i=0;i<=N;++i)for(int j=0;j<=N;++j)
    ans=min(ans,t1[i]+t2[j]+dis(i,j)/r);
    printf("%.2lf\n",ans);return 0;
}

想到了一种 $O(1)$ 做法（如果开根算 $O(1)$ 的话）。但是这种方法讨论的情况有点多，题目测试点又不多，所以有可能存在点问题。欢迎 hack。

思路

分情况讨论并通过一些数学运算求解。

易得至少存在一条最优路径，满足其可以分解为三条线段，即在线段 $AB$ 上走一段、在平面的其它地方走一段、在线段 $CD$ 上走一段。

先考虑一个简单一点的问题：

从 $A$ 点经 $C$ 点到 $D$ 点，其中在直线 $CD$ 上移动一个单位长度需要 $Q$ 的时间，在平面内其它位置移动一个单位长度需要 $R$ 的时间，保证 $R>Q>0$。（注意这里为了方便，将题面中的 $\frac{1}{P}$ 记为 $P$，$\frac{1}{Q}$ 记为 $Q$，$\frac{1}{R}$ 记为 $R$，与题面有一定差异。）

其中 $h$、$l$ 为定值，设路径耗时为 $f(x)$，求 $x$ 为何值时，$f(x)$ 最小与对应的最小值。

经过一些计算，可以发现 $f(x)$ 是单峰函数，$f(x)$ 最小时，$x=\frac{Qd}{\sqrt{R^2-Q^2}}$，此时 $f(x)_{min}=\sqrt{R^2-Q^2}h+Ql$

为了叙述简便，下文中将上述路径称为点到传送带的最优路径。

另一个简单一点的问题：

如果题目中的传送带不是线段而是直线，证明：存在最优路径，满足它可以被划分为不多于两个线段。也就是说不会既在 $AB$ 上走一段、在平面中其它位置走一段，又在 $CD$ 上走一段，三者至多有其二。

首先考虑两条直线相交的情况：

考虑路径 $A \to E \to D$ 和 $A \to M \to N \to D$，后者对比前者，可以理解为用路径 $M \to N$ 代替了路径 $M \to E \to N$。如图作 $M'N' // MN$， 若 $M \to N$ 比 $M \to E \to N$ 用时更短，由相似可知 $M' \to N'$ 比 $M' \to E \to N'$ 用时更短，且两路径用时差值增大，所以路径 $A \to M' (\to N') \to D$ 比 $A \to M \to N \to D$ 更优，且以此方式作出的最优路径一定能被划分成不多于两个线段。

再考虑两条直线平行的情况：

这样的情况下，你在直线 $AB$ 上和 $CD$ 上走相同的距离产生的位移是相同的，那明显在更快的传送带上走更省时间，慢一点的传送带干脆别走了，这样才能达到最优解。两个传送带，你只能走一个，路径肯定能被分成不多于两个线段。

得出这个结论后，你可以以 $A, B, C, D$ 四个点分别为起点，做四次三分，而不用三分套三分了。（我试了从四个起点开始做四次暴力，可以过。）

原题思路

由上面两个问题得出，最优解的可能无非就是：$A \to B \to C \to D, A \to B \to D, A \to C \to D, A \to D$ 或者先走到 $A, B, C, D$ 中的某个点，之后走第一个小问题推出来的最优路径到对面的传送带，再走到对面的终点（正着走和倒着走都需要考虑）。

需要注意最优路径走出来的拐点有时候不在线段上，这时候需要舍弃。

把上述所有方案枚举一遍即可。

计算最优路径时如果硬算可能有些麻烦，我采取的方案是以 $\vec{AB}$ 为 $x$ 轴正方向重新建系（或者也可以理解为把坐标系平移旋转一下），算出最优路径出发点的新坐标，这样整个图形就被正过来了，好算了很多。

代码

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

// 数学里的向量，和坐标是近义词，和变长数组不是近义词
struct Vector {
    double x, y;
    //向量加
    Vector operator+(const Vector b) {
        return { x + b.x, y + b.y };
    }
    //向量减
    Vector operator-(const Vector b) {
        return { x - b.x, y - b.y };
    }
    //向量数量积
    double operator*(const Vector b) {
        return x * b.x + y * b.y;
    }
    //向量模长
    double len() {
        return sqrt(x * x + y * y);
    }
};

double p, q, r; //题目中的速度，但为了方便被修改成了题面中的 1/p, 1/q, 1/r
double ans;

/// @brief 计算最优路径的函数。
/// @param l 传送带的起点 L（A 点或 D 点）。
/// @param lr 传送带对应的向量 LR。
/// @param p 最优路径起始点（题解图中的 A）。
/// @param len 向量 LR 的模长（之前算过了，所以为了让程序跑得快一点就不重新算一遍了）。
/// @param t 在传送带上走一个单位长度所需的时间（p 或 q）。
/// @return 最优路径长度，若最优路径不合法，则返回 INFINITY（正无穷）。
double calc(Vector l, Vector lr, Vector p, double len, double t) {
    if (len == 0 || t >= r)
        return INFINITY;
    const Vector new_x({ lr.x / len, lr.y / len }); //指向新坐标系的 x 方向的单位向量
    const Vector new_y({ new_x.y, -new_x.x });      //指向新坐标系的 y 方向的单位向量
    const Vector new_p({ (p - l) * new_x, abs((p - l) * new_y) });  //p 点在新坐标系中的坐标（若 y 坐标是负的则轴对称一下，保证它在第一或二象限）
    if (new_p.x <= 0)
        return INFINITY;    //若在第二象限，则最优路径不合法（默认最优路径是向左的，因为传送带末端在起点的右边）。
    const double inflexion = new_p.x - t * new_p.y / sqrt(r * r - t * t);    //最优路径拐点 x 坐标。
    if (inflexion <= 0 || inflexion >= len)
        return INFINITY;    //若拐点不在传送带上，则最优路径不合法。
    return sqrt(r * r - t * t) * new_p.y + t * new_p.x; //返回最优路径长度。
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    Vector a, b, c, d;  //题目中的 A, B, C, D。
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y >> p >> q >> r;
    p = 1 / p, q = 1 / q, r = 1 / r;
    Vector ab = b - a, dc = c - d;
    const double l_ab = ab.len(), l_dc = dc.len();
    ans = min({
        l_ab * p + l_dc * q + (c - b).len() * r,
        l_ab * p + (d - b).len() * r,
        l_dc * q + (a - c).len() * r,
        (d - a).len() * r
    }); //A, B, C, D 四个点连线的四种情况取最优解。
    //从 A, B, C, D 开始走最优路径的情况取最优解。
    ans = min(ans, calc(a, ab, d, l_ab, p));
    ans = min(ans, calc(d, dc, a, l_dc, q));
    ans = min(ans, calc(a, ab, c, l_ab, p) + l_dc * q);
    ans = min(ans, calc(d, dc, b, l_dc, q) + l_ab * p);
    cout << fixed << setprecision(2) << ans << '\n';
    return 0;
}

这题好像是以前一次训练赛的赛题，当时尝试推导过数学做法但是失败了。退役之后偶然翻到以前的草稿纸，于是继续研究，凑出来了这种方法。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;	//我一般喜欢把eps设为1e-8，当然对于这题1e-6足够了
double ax, ay, bx, by, cx, cy, dx, dy, p, q, r;
double dis(double x_1, double y_1, double x_2, double y_2) {	//P1和P2的距离
    double xdis = x_1 - x_2, ydis = y_1 - y_2;
    return sqrt(xdis * xdis + ydis * ydis);
}
double f(double x_1, double y_1, double x_2, double y_2) {	//上文中提到的f(P1)在当F是P2时的值
    return dis(x_1, y_1, x_2, y_2) / r + dis(x_2, y_2, dx, dy) / q;
    //第一个是dis(E,F)/r，第二个是dis(F,D)/q
}
double calc1(double x, double y) {	//内层三分F（这个给定的参数是固定E是这个点）
    double lx = cx, ly = cy, rx = dx, ry = dy;	//在CD上三分
    while (dis(lx, ly, rx, ry) > eps) {	//还没有重合成一点
        double tmpx = (rx - lx) / 3, tmpy = (ry - ly) / 3;
        double lmidx = lx + tmpx, rmidx = rx - tmpx, lmidy = ly + tmpy, rmidy = ry - tmpy;	//(lmidx,lmidy)是左等分点，(rmidx,rmidy)是右等分点
        double 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);	//返回这个最小值
}
double calc() {	//外层三分E
    double lx = ax, ly = ay, rx = bx, ry = by;	//在AB上三分
    while (dis(lx, ly, rx, ry) > eps) {
        double tmpx = (rx - lx) / 3, tmpy = (ry - ly) / 3;
        double lmidx = lx + tmpx, rmidx = rx - tmpx, lmidy = ly + tmpy, rmidy = ry - tmpy;	//以上同理
        double ans1 = calc1(lmidx, lmidy) + dis(ax, ay, lmidx, lmidy) / p, ans2 = calc1(rmidx, rmidy) + dis(ax, ay, rmidx, rmidy) / p;	//左等分点和右等分点的值（在这里套了内层三分）
        if (ans2 - ans1 > eps) rx = rmidx, ry = rmidy;
        else lx = lmidx, ly = lmidy;	//同理
    }
    return calc1(lx, ly) + dis(ax, ay, lx, ly) / p;	//返回最小值，也就是答案
}
int main() {
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy, &p, &q, &r);
    printf("%.2lf\n", calc());	//这就是答案
}