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

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[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 LOCALfreopen(&#","r",stdin);
#endifscanf("%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("%.18lfn",t);}else {printf("%.18lfn", MinTime(x[0]+(v[0]-w[0])*t0, y[0]+(v[1]-w[1])*t0, w[0], w[1]));}return 0;
}

转载于:.html