Codeforces Round #327 590B Chip 'n Dale Rescue Rangers（等效转换，二分）

t和可到达具有单调性，二分就不多说了。下面说下O(1)的做法，实际上是等效转换，因为答案一定存在，如果在t₀之前，那么分解一下

直接按照只有v计算就可以了。反过来如果计算的结果大于t0，那么表示答案在t₀之后。因为速度分量是可以独立累加的，因此

可以找到一开始就只有w的等效的点。

#include<bits/stdc++.h>

using namespace std;

double x[], y[];

double vm, t0;

double v[], w[];

const double eps = 1e-;

double dex, dey, D;

bool unitization(double &dx = dex, double &dy = dey)

{

    D = hypot(dx, dy);

    if(D > eps){

        dx /= D; dy /= D;

        return true;

    }

    return false;

}

inline double Dot(double vx, double vy)

{

    return dex*vx + dey*vy;

}

inline double Cross(double vx, double vy)

{

    return dex*vy - dey*vx;

}

inline double MinTime(double x0, double y0, double vx, double vy, double x1 = x[], double y1 = y[])

{

    dex = x1-x0; dey = y1-y0;

    if(!unitization()) return ;

    double vh = Cross(vx,vy);

    double vn = Dot(vx,vy);

    double vc = vn + sqrt(vm*vm - vh*vh);

    return D/vc;

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    scanf("%lf%lf%lf%lf", x, y, x+, y+);

    scanf("%lf%lf", &vm, &t0);

    scanf("%lf%lf%lf%lf", v, v+, w, w+);

    double t = MinTime(x[], y[], v[], v[]);

    if(t0 >= t){

        printf("%.18lf\n",t);

    }else {

        printf("%.18lf\n", MinTime(x[]+(v[]-w[])*t0, y[]+(v[]-w[])*t0, w[], w[]));

    }

    return ;

}

巴特西

Codeforces Round #327 590B Chip 'n Dale Rescue Rangers（等效转换，二分）

最新文章

热门文章