Codeforces 591D Chip 'n Dale Rescue Rangers

Codeforces 591D Chip 'n Dale Rescue Rangers

题目链接：CF-591D

题意：有两个点（x1，y1），（x2，y2）。在（x1，y1）这个点有一个飞船，它相对与风的最大速度为vmax，而且可以在任意时刻调整自己的速度大小和方向。根据天气预测，在前T秒内，风速向量为（ux，uy），T秒过后变成（wx，wy），求从第一个点到第二个点的最短时间。 思路：二分时间。 根据运动的独立性，我们可以先考虑由于风速对（x1，y1）造成的影响，显然如果在时间t内，t>T时，飞船的新坐标是（x1+ux*T+wx*(t-T),y1+uy*T+wy*(t-T)）；如果t<T,则新坐标是（x1+ux*t,y1+uy*t），接下来再考虑新坐标与（x2，y2）两点间的距离，如果在t时间内，t*vmax>两点间的距离，则在t时间内飞船可以完成从（x1，y1）到达（x2，y2）的任务，否则不能。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;int x_1, y_1, x_2, y_2, vmax, t, ux, uy, wx, wy;bool ok(double tt)
{double sub = tt - t;double curx=x_1, cury=y_1;if ( sub >= 0 ){curx += (ux*t+wx*sub);cury += (uy*t+wy*sub);}else{curx += ux*tt;cury += uy*tt;}if ((x_2 - curx)*(x_2 - curx) + (y_2 - cury)*(y_2 - cury) <= vmax*vmax*tt*tt)return true;elsereturn false;
}int main() {scanf("%d%d%d%d%d%d%d%d%d%d", &x_1, &y_1, &x_2, &y_2, &vmax, &t,&ux,&uy,&wx,&wy);double left = 0, right = 1e9;double mid;int cnt = 0;while (cnt<1e6){mid = (left + right)/2;if (ok(mid))right = mid;elseleft = mid;cnt++;}printf("%lfn", right);
//	system("pause");return 0;
}