首页 > 其他 > 详细

Codeforces Round #327 590B Chip 'n Dale Rescue Rangers

时间:2015-11-03 22:40:59      阅读:287      评论:0      收藏:0      [点我收藏+]

二分就不多说了,下面说下O(1)的做法,实际上是等效转化,因为答案一定存在,如果在t0之前,那么分解一下

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

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

#include<bits/stdc++.h>
using namespace std;

double x[2], y[2];
double vm, t0;
double v[2], w[2];

const double eps = 1e-11;
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[1], double y1 = y[1])
{
    dex = x1-x0; dey = y1-y0;
    if(!unitization()) return 0;
    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+1, y+1);
    scanf("%lf%lf", &vm, &t0);
    scanf("%lf%lf%lf%lf", v, v+1, w, w+1);
    double t = MinTime(x[0], y[0], v[0], v[1]);
    if(t0 >= t){
        printf("%.18lf\n",t);
    }else {
        printf("%.18lf\n", MinTime(x[0]+(v[0]-w[0])*t0, y[0]+(v[1]-w[1])*t0, w[0], w[1]));
    }
    return 0;
}

 

Codeforces Round #327 590B Chip 'n Dale Rescue Rangers

原文:http://www.cnblogs.com/jerryRey/p/4934378.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!