[SCOI 2010]传送带

Description

题库链接

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

\(1\leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\leq 1000,1\leq P,Q,R\leq 10\)

Solution

我们大胆猜想小心求证。我们猜测当我们来枚举在 \(AB\) 上的离开点和 \(CD\) 上的进入点时，是两个单峰函数。

那么直接用三分法求解了。注意要特判线段退化成点的情况。

至于证明，都说了小心求证。详见链接：->戳我<-

Code

//It is made by Awson on 2018.3.1

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const double eps = 1e-4;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }

double xa, ya, xb, yb, xc, yc, xd, yd, p, q, r, ans;

double e, f, g, h, i, j;

double dist(double a, double b, double c, double d) {

#define sqr(x) ((x)*(x))

    double ans = 0;

    ans += sqrt(sqr(a-e)+sqr(b-f))/p;

    ans += sqrt(sqr(a-c)+sqr(b-d))/r;

    ans += sqrt(sqr(c-g)+sqr(d-h))/q;

    return ans;

}

double count(double x, double y) {

    xc = i, yc = j, xd = g, yd = h;

    double ans = dist(x, y, xd, yd);

    while (true) {

    if (fabs(yc-yd) <= eps && fabs(xc-xd) <= eps) break;

    double xm1 = (xc*2+xd)/3., xm2 = (xc+xd*2)/3.;

    double ym1 = (yc*2+yd)/3., ym2 = (yc+yd*2)/3.;

    double c1 = dist(x, y, xm1, ym1), c2 = dist(x, y, xm2, ym2);

    if (c1 > c2) xc = xm1, yc = ym1, ans = c2; else xd = xm2, yd = ym2, ans = c1;

    }

    return ans;

}

void work() {

    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &xa, &ya, &xb, &yb, &xc, &yc, &xd, &yd, &p, &q, &r);

    e = xa, f = ya, g = xd, h = yd, i = xc, j = yc; ans = count(xa, ya);

    while (true) {

    if (fabs(ya-yb) <= eps && fabs(xa-xb) <= eps) break;

    double xm1 = (xa*2+xb)/3., xm2 = (xa+xb*2)/3.;

    double ym1 = (ya*2+yb)/3., ym2 = (ya+yb*2)/3.;

    double c1 = count(xm1, ym1), c2 = count(xm2, ym2);

    if (c1 > c2) xa = xm1, ya = ym1, ans = c2; else xb = xm2, yb = ym2, ans = c1;

    }

    printf("%.2lf\n", ans);

}

int main() {

    work(); return 0;

}