D. Chip 'n Dale Rescue Rangers
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/591/problem/D
Description
We assume that the action takes place on a Cartesian plane. The headquarters of the rescuers is located at point (x1, y1), and the distress signal came from the point (x2, y2).
Due to Gadget's engineering talent, the rescuers' dirigible can instantly change its current velocity and direction of movement at any moment and as many times as needed. The only limitation is: the speed of the aircraft relative to the air can not exceed meters per second.
Of course, Gadget is a true rescuer and wants to reach the destination as soon as possible. The matter is complicated by the fact that the wind is blowing in the air and it affects the movement of the dirigible. According to the weather forecast, the wind will be defined by the vector (vx, vy) for the nearest t seconds, and then will change to (wx, wy). These vectors give both the direction and velocity of the wind. Formally, if a dirigible is located at the point (x, y), while its own velocity relative to the air is equal to zero and the wind (ux, uy) is blowing, then after seconds the new position of the dirigible will be .
Gadget is busy piloting the aircraft, so she asked Chip to calculate how long will it take them to reach the destination if they fly optimally. He coped with the task easily, but Dale is convinced that Chip has given the random value, aiming only not to lose the face in front of Gadget. Dale has asked you to find the right answer.
It is guaranteed that the speed of the wind at any moment of time is strictly less than the maximum possible speed of the airship relative to the air.
Input
The first line of the input contains four integers x1, y1, x2, y2 (|x1|, |y1|, |x2|, |y2| ≤ 10 000) — the coordinates of the rescuers' headquarters and the point, where signal of the distress came from, respectively.
The second line contains two integers and t (0 < v, t ≤ 1000), which are denoting the maximum speed of the chipmunk dirigible relative to the air and the moment of time when the wind changes according to the weather forecast, respectively.
Next follow one per line two pairs of integer (vx, vy) and (wx, wy), describing the wind for the first t seconds and the wind that will blow at all the remaining time, respectively. It is guaranteed that and
.
Output
Print a single real value — the minimum time the rescuers need to get to point (x2, y2). You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .
Sample Input
0 0 5 5
3 2
-1 -1
-1 0
Sample Output
3.729935587093555327
HINT
题意
你一开始在x1,y1，你要走到x2,y2,但是这时候有风，风在t秒前风速是(vx,vy)在t秒后，风速是(wx,wy)
你和风的相对速度，最多差距vmax，保证vmax大于风速，然后问你，最少什么时候到达
题解：
反着做，把坐标系变成风，那么就可以看做终点加了一个和风相反的速度，然后你负责追它就好了
二分时间，然后跑
但是，二分的时候，千万不要用eps，直接for就好了
代码
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
double eps = 1e-;
double dis(double x1,double yy1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(yy1-y2)*(yy1-y2));
}
double yy1;
double x1,x2,y2,v,t,vx,vy,wx,wy;
int check(double tt)
{
double xx=x2,yy=y2;
if(tt<=t)
{
xx = xx + -vx * tt;
yy = yy + -vy * tt;
}
else
{
xx = xx + -vx * t + -wx * (tt - t);
yy = yy + -vy * t + -wy * (tt - t);
}
if(dis(x1,yy1,xx,yy)<=tt*v)
return ;
return ;
}
int main()
{
cin>>x1>>yy1>>x2>>y2>>v>>t>>vx>>vy>>wx>>wy;
double l = 0.00,r = t;
for(int i=;i<=;i++)
{
double mid = (l+r)/2.0;
if(check(mid))r=mid;
else l=mid;
}
if(check(t))
{
printf("%.12lf\n",l);
return ;
}
l = t, r = 9999999999.0;
for(int i=;i<=;i++)
{
double mid = (l+r)/2.0;
if(check(mid))r=mid;
else l=mid;
}
printf("%.12lf\n",l);
}