bzoj 1857: [Scoi2010]传送带三分

1857: [Scoi2010]传送带

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 934 Solved: 501
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

三分套三分就可以了

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

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

double dis(double x1, double y1, double x2, double y2) {

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

double ternary(double x, double y) {

    double lx = xc, ly = yc, rx = xd, ry = yd;

    while(fabs(rx-lx)>eps || fabs(ry-ly)>eps) {

        double x1 = lx+(rx-lx)/, x2 = lx+(rx-lx)/*;

        double y1 = ly+(ry-ly)/, y2 = ly+(ry-ly)/*;

        double tmp1 = dis(x, y, x1, y1)/r+dis(x1, y1, xd, yd)/q+dis(x, y, xa, ya)/p;

        double tmp2 = dis(x, y, x2, y2)/r+dis(x2, y2, xd, yd)/q+dis(x, y, xa, ya)/p;

        if(tmp1>tmp2) {

            lx = x1, ly = y1;

        } else {

            rx = x2, ry = y2;

        }

    }

    return dis(x, y, lx, ly)/r+dis(lx, ly, xd, yd)/q+dis(x, y, xa, ya)/p;

}

double solve() {

    double lx = xa, rx = xb, ly = ya, ry = yb;

    while(fabs(rx-lx)>eps || fabs(ry-ly)>eps) {

        double x1 = lx+(rx-lx)/, x2 = lx+(rx-lx)/*;

        double y1 = ly+(ry-ly)/, y2 = ly+(ry-ly)/*;

        double tmp1 = ternary(x1, y1), tmp2 = ternary(x2, y2);

        if(tmp1>tmp2) {

            lx = x1, ly = y1;

        } else {

            rx = x2, ry = y2;

        }

    }

    return ternary(lx, ly);

}

int main()

{

    cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd>>p>>q>>r;

    double ans = solve();

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

    return ;

}

传送带