题目描述

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

题解

首先要吐槽一下数据，不。。应该是我sadiao了。。。qwq没有想到有两个点重合在一起就炸掉的情况。
很多人都用了SA过的，但是三分更好写，个人感觉。
非常容易可以得出，我们的答案分成3个部分，在线段ab，平面内和线段cd上。
\[ans=min(\frac{dis(a,b)}{p}+\frac{dis(e,f)}{q}+\frac{dis(f,d)}{r})\]
以上式子中的e和f就是在线段ab和线段cd上的某一个点，这个答案就是最小的。
首先，很多人好像不知道怎么三分，其实比较简单，将线段x和y坐标都三等分。。
将e这个点当做一个定点，这样可以三分出e当前的最优的f点的答案。再对e三分。
三分套三分，代码还算简单。细节需要注意一下。

代码

#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
using namespace std;
const double eps = 1e-8;
db ax, ay, bx, by, cx, cy, dx, dy, p, q, r;
template <typename T>
T sqr(T x) {
    return x * x;
}
db dist(db x1, db y1, db x2, db y2) {
    return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
db calc(db x, db y) {
    db lx = cx, ly = cy, rx = dx, ry = dy;
    while (dist(lx, ly, rx, ry) > eps) {
        db Dx = (rx - lx) / 3.0, Dy = (ry - ly) / 3.0;
        db midlx = lx + Dx, midly = ly + Dy, midrx = rx - Dx, midry = ry - Dy;
        db tmp1 = (dist(x, y, midlx, midly) / r) + (dist(dx, dy, midlx, midly) / q), tmp2 = (dist(x, y, midrx, midry) / r) + (dist(dx, dy, midrx, midry) / q);
        if (tmp2 - tmp1 > eps) rx = midrx, ry = midry;
        else lx = midlx, ly = midly;
    }
    return (dist(x, y, lx, ly) / r) + (dist(dx, dy, lx, ly) / q);
}
int main() {
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy, &p, &q, &r);
    db lx = ax, ly = ay, rx = bx, ry = by;
    while (dist(lx, ly, rx, ry) > eps) {
        db Dx = (rx - lx) / 3.0, Dy = (ry - ly) / 3.0;
        db midlx = lx + Dx, midly = ly + Dy, midrx = rx - Dx, midry = ry - Dy;
        db tmp1 = calc(midlx, midly) + (dist(ax, ay, midlx, midly) / p), tmp2 = calc(midrx, midry) + (dist(ax, ay, midrx, midry) / p);
        if (tmp2 - tmp1 > eps) rx = midrx, ry = midry;
        else lx = midlx, ly = midly;
    }
    printf("%.2lf\n", calc(lx, ly) + dist(ax, ay, lx, ly) / p);
    return 0;
}

巴特西

[luogu2571][bzoj1857][SCOI2010]传送门【三分套三分】

题目描述

题解

代码

最新文章

热门文章