题目地址：洛谷：【P2571】[SCOI2010]传送带 – 洛谷、BZOJ：Problem 1857. — [Scoi2010]传送带

题目描述

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间

输入输出格式

输入格式：
输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy
第三行是3个整数，分别是P，Q，R

输出格式：
输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位

输入输出样例

输入样例#1：

0 0 0 100
100 0 100 100
2 2 1

输出样例#1：

136.60

说明

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000，1<=P，Q，R<=10

题解

我们在AB上取一个点E，CD上取一个点F，路径一定是A→E→F→D这样的。我们来大胆猜测一波，如果固定E，时间关于F在CD上的位置是一个单峰有最小值的函数，再猜测总时间关于E在AB上的位置也是这样一个函数，那么我们就可以三分套三分来解决这个问题。可是我不会证明啊QAQ
三分法是用于解决单峰函数找最值的问题的方法，具体操作可以参见【P3382】【模板】三分法 – 洛谷。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cmath>

const double EPS = 1e-8;

double ax, ay, bx, by, cx, cy, dx, dy, p, q, r;

// E on AB, F on CD
inline double caltime(double ex, double ey, double fx, double fy) {
    return sqrt((ex - ax) * (ex - ax) + (ey - ay) *(ey - ay)) / p
        + sqrt((dx - fx) * (dx - fx) + (dy - fy) *(dy - fy)) / q
        + sqrt((ex - fx) * (ex - fx) + (ey - fy) *(ey - fy)) / r;
}

inline double terCD(double ex, double ey) {
    double l = 0, r = 1, mid, midd;
    while(r - l > EPS) {
        mid = (l + r) / 2; midd = (mid + r) / 2;
        if(caltime(ex, ey, cx + (dx - cx) * mid, cy + (dy - cy) * mid) < 
            caltime(ex, ey, cx + (dx - cx) * midd, cy + (dy - cy) * midd)) {
            r = midd;
        } else {
            l = mid;
        }
    }
    return caltime(ex, ey, cx + (dx - cx) * l, cy + (dy - cy) * l);
}

inline double terAB() {
    double l = 0, r = 1, mid, midd;
    while(r - l > EPS) {
        mid = (l + r) / 2; midd = (mid + r) / 2;
        if(terCD(ax + (bx - ax) * mid, ay + (by - ay) * mid) <
            terCD(ax + (bx - ax) * midd, ay + (by - ay) * midd)) {
            r = midd;
        } else {
            l = mid;
        }
    }
    return terCD(ax + (bx - ax) * l, ay + (by - ay) * l);
}

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, &r);
    printf("%.2lf", terAB());
    return 0;
}