BZOJ1857【SCOI2010】传送带 <三分法>

Problem

【SCOI2010】传送带

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

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

Input

输入数据第一行是$4$个整数，表示$A$和$B$的坐标，分别为$A_x,A_y,B_x,B_y$。
第二行是$4$个整数，表示$C$和$D$的坐标，分别为$C_x,C_y,D_x,D_y$。
第三行是$3$个整数，分别是$P,Q,R$。

Output

输出数据为一行，表示$\mathrm{lxhgww}$从$A$点走到$D$点的最短时间，保留到小数点后$2$位。

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

Hint

对于$100\%$的数据，$1\le A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\le10^3$，$1\le P,Q,R\le10$。

标签：三分法

Solution

三分套三分，据说有大学物理结论可以$\mathrm{O(1)}$做…
首先一定是从$A$走到$AB$上的一点$E$，然后走平面到$CD$上的一点$F$，最后从$F$沿$CD$走到$D$。
考虑确定$AB$上的$E$点，那么若将$F$点的所有位置都计算答案并画成函数图像，一定是一个单峰函数。那么确定$E$后可以三分法找到最佳$F$位置。
同样地，对于每个$E$位置的最佳答案，也会呈一个单峰函数。因此可以先对$E$在$AB$上进行三分，每次三分到的两个端点需要再对$F$在$CD$上进行三分找到最小时间。
这样一来，可以先在$AB$上三分$E$，每次三分找端点最值的时候再在$CD$上三分$F$，三分套三分即可找到答案。

Code

#include <bits/stdc++.h>
#define EPS 1e-4
#define xx first
#define yy second
#define mp make_pair
#define pdd pair<dnt,dnt>
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
pdd A, B, C, D;    dnt P, Q, R;
dnt sqr(dnt x) {return x*x;}
dnt dis(pdd x, pdd y) {return sqrt(sqr(x.xx-y.xx)+sqr(x.yy-y.yy));}
dnt tri_search_T(pdd l, pdd r, pdd S) {
    dnt ret = dis(A, S)/dis(l, D)/Q+dis(S, l)/R;	pdd llr, lrr;
    while (fabs(l.xx-r.xx) > EPS || fabs(l.yy-r.yy) > EPS) {
        llr = mp(l.xx+(r.xx-l.xx)/3, l.yy+(r.yy-l.yy)/3);
        lrr = mp(r.xx-(r.xx-l.xx)/3, r.yy-(r.yy-l.yy)/3);
        dnt tllr = dis(A, S)/P+dis(llr, D)/Q+dis(S, llr)/R;
        dnt tlrr = dis(A, S)/P+dis(lrr, D)/Q+dis(S, lrr)/R;
        if (tllr < tlrr) r = lrr; else l = llr;
        ret = min(tllr, tlrr);
    }
    return ret;
}
dnt tri_search_S(pdd l, pdd r) {
    dnt ret = tri_search_T(C, D, l);	pdd llr, lrr;
    while (fabs(l.xx-r.xx) > EPS || fabs(l.yy-r.yy) > EPS) {
        llr = mp(l.xx+(r.xx-l.xx)/3, l.yy+(r.yy-l.yy)/3);
        lrr = mp(r.xx-(r.xx-l.xx)/3, r.yy-(r.yy-l.yy)/3);
        dnt tllr = tri_search_T(C, D, llr);
        dnt tlrr = tri_search_T(C, D, lrr);
        if (tllr < tlrr) r = lrr; else l = lrr;
        ret = min(tllr, tlrr);
    }
    return ret;
}
int main() {
    read(A.xx), read(A.yy), read(B.xx), read(B.yy);
    read(C.xx), read(C.yy), read(D.xx), read(D.yy);
    read(P), read(Q), read(R);
    return printf("%.2lf\n", tri_search_S(A, B)), 0;
}