传送带

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1617 字
三分套三分确定两段传送带的进出点
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1439
// 题意：两条线段传送带 AB 和 CD，在 AB 上速度为 P、CD 上为 Q、平面上为 R，求从 A 到 D 的最短时间，保留 2 位小数。
// 思路：三分套三分。
// 1. 外层三分 AB 上的出发点 E（用参数 t1 表示位置）。
// 2. 内层三分 CD 上的离开点 F，总时间 = |AE| / P + |EF| / R + |FD| / Q。
// 3. 固定 E 时总时间关于 F 是单峰的，固定 F 最优后总时间关于 E 也是单峰的，所以可以嵌套三分。
// 复杂度：O(log^2(1/eps)) 时间 / O(1) 空间
// 易错点：三段路程的速度各不相同，别把 |AE| 和 |FD| 也按平面速度 R 计算。
// 易错点：三分迭代次数要足够（80 次以上），否则两位小数会抖。
#include <bits/stdc++.h>
using namespace std;
struct Point {
    double x, y;
};
Point A, B, C, D;
double P, Q, R;
double len(Point a, Point b){
    return hypot(a.x - b.x, a.y - b.y);
}
Point onLine(Point s, Point t, double k){
    return {s.x + (t.x - s.x) * k, s.y + (t.y - s.y) * k};
}
double inner(Point e){
    double l = 0, r = 1;
    auto cost = [&](double k){
        Point f = onLine(C, D, k);
        return len(e, f) / R + len(f, D) / Q;
    };
    for(int it = 0; it < 80; it++){
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if(cost(m1) < cost(m2)) r = m2;
        else l = m1;
    }
    return cost((l + r) / 2);
}
int main(){
    if(!(cin >> A.x >> A.y >> B.x >> B.y)) return 0;
    if(!(cin >> C.x >> C.y >> D.x >> D.y)) return 0;
    if(!(cin >> P >> Q >> R)) return 0;
    double l = 0, r = 1;
    auto calc = [&](double k){
        Point e = onLine(A, B, k);
        return len(A, e) / P + inner(e);
    };
    for(int it = 0; it < 80; it++){
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if(calc(m1) < calc(m2)) r = m2;
        else l = m1;
    }
    cout << fixed << setprecision(2) << calc((l + r) / 2) << "\n";
    return 0;
}
传送带

正文

一本通·提高篇的其它内容
