学步园

【题目描述】
在一个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位
【样例输入】
0 0 0 100
100 0 100 100
2 2 1
【样例输出】
136.60
【数据范围】
对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10

代码不算长，只是其中加了个Point类（可供坐标的加减乘除运算），占了一定篇幅。

此题考察三分法。

原问题可以抽象成以下问题：
在线段AB上找一点E，在线段CD上找一点F，使得AE / p + EF / r + FD / q最小。

不难看出，E，F点一定是唯一的。
也就是说，关于E，F的目标函数在定义域内一定只有一个极值点。
那么可以直接三分E和F，求得最小值即可。

Accode：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

const double MAX = 1e198;
const double MIN = -MAX;
const double zero = 1e-12;

template <typename _Tp>
class Point
{
private:
    _Tp _x, _y;
public:
    Point() {_x = _y = 0; }
    Point(_Tp x, _Tp y)
    {
        _x = x;
        _y = y;
    }
    _Tp x();
    _Tp y();
    Point &operator=(Point p)
    {
        _x = p.x();
        _y = p.y();
        return *this;
    }
    Point operator+(Point b) const
    {
        Point c(_x + b.x(), _y + b.y());
        return c;
    }
    Point operator-(Point b) const
    {
        Point c(_x - b.x(), _y - b.y());
        return c;
    }
    Point operator*(_Tp p)
    {
        Point c(_x * p, _y * p);
        return c;
    }
    Point operator/(_Tp p)
    {
        Point c(_x / p, _y / p);
        return c;
    }
    Point &operator+=(Point b)
    {
        _x += b.x();
        _y += b.y();
        return *this;
    }
    Point &operator-=(Point b)
    {
        _x -= b.x();
        _y -= b.y();
        return *this;
    }
    Point &operator*=(_Tp p)
    {
        _x *= p;
        _y *= p;
        return *this;
    }
    Point &operator/=(_Tp p)
    {
        _x /= p;
        _y /= p;
        return *this;
    }
};

int xA, xB, xC, xD, yA, yB, yC, yD;
Point <double> A, B, C, D;
double v1, v2, v3;

template <typename _Tp>
_Tp Point <_Tp> ::x()
{
    return _x;
}

template <typename _Tp>
_Tp Point <_Tp> ::y()
{
    return _y;
}

double sqr(double x)
{
    return x * x;
}

double dist(Point <double> a,
            Point <double> b)
{
    Point <double> tmp = b - a;
    return sqrt(sqr(tmp.x()) + sqr(tmp.y()));
}

double func(Point <double> E,
            Point <double> F)
{
    return dist(A, E) / v1
    + dist(E, F) / v3
    + dist(F, D) / v2;
}

double Find_F(Point <double> E)
{
    Point <double> L = C, R = D, tmp, p, q;
    double ans = MAX;
	//一切的枚举变量都应使用局部变量。
    while (dist(L, R) > zero)
    {
        tmp = (R - L) / 3;
        p = L + tmp;
        q = R - tmp;
        double fp = func(E, p);
        double fq = func(E, q);
        if (fp > fq) L = p;
        else R = q;
        if (fp < ans) ans = fp;
        if (fq < ans) ans = fq;
	//更新ans的值。
    }
    if (dist(C, D) < zero) ans = func(E, C);
	//特殊处理，当C，D重合时，F取C。
    return ans;
}

double Find_E()
{
    Point <double> L = A, R = B, tmp, p, q;
    double ans = MAX;
	//一切的枚举变量都应使用局部变量。
    while (dist(L, R) > zero)
    {
        tmp = (R - L) / 3;
        p = L + tmp;
        q = R - tmp;
        double fp = Find_F(p);
        double fq = Find_F(q);
        if (fp > fq) L = p;
        else R = q;
        if (fp < ans) ans = fp;
        if (fq < ans) ans = fq;
	//更新ans的值。
    }
    if (dist(A, B) < zero) ans = Find_F(A);
	//特殊处理：当A，B重合时，E取A。
    return ans;
}

int main()
{
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout);
    scanf("%d%d%d%d%d%d%d%d%lf%lf%lf",
          &xA, &yA, &xB, &yB, &xC, &yC,
          &xD, &yD, &v1, &v2, &v3);
    A = Point <double> (xA, yA);
    B = Point <double> (xB, yB);
    C = Point <double> (xC, yC);
    D = Point <double> (xD, yD);
    printf("%.2lf\n", Find_E());
	return 0;
}