CF 590B Chip 'n Dale Rescue Rangers(二分)

CF 590B Chip 'n Dale Rescue Rangers(二分)

【题目链接】：click here~~

【题目大意】：给你一个初始坐标，救援坐标，从初始坐标到救援坐标飞行的过程中会受到风力的影响（包括风力的方向和速度）0到t时间内，风力向量为(vx,vy)，之后变为(wx,wy)

注意飞行器可以在任意一个时刻随时变换方向和速度，但速度最大值不能超过V，求到达救援坐标的最少时间。

【思路】：

CF#327 div 2的D题，题面题意理解很重要，理解之后就不难想到，在t时间之后，因为风力是时刻在影响飞行器的速度，要求最小时间，所以可以二分时间，在时间的确定的情况下，可以得到飞行器的位移，从而判断速度和最大值的关系。

代码：

/*
* Problem:CodeForces 590B - Chip 'n Dale Rescue Rangers
* Running time: 4MS
* Complier: G++
* Author: herongwei
* Create Time: 20:20 2015/10/27 星期二
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;const int maxn=1e5+10;
const double eps=1e-8;
const double inf=1e10;
double x1,y1,x2,y2;
double v,t;
double vx,vy,wx,wy;
double sqr(double x) {return x*x;}
double dis(double x1,double y1,double x2,double y2)
{return (double)(sqr(x1-x2)+sqr(y1-y2));
}
bool judge(double x)
{double tx,ty;if(x>t){tx=x1+vx*t+wx*(x-t);ty=y1+vy*t+wy*(x-t);}else{tx=x1+vx*x;ty=y1+vy*x;}double d=dis(tx,ty,x2,y2);if(d<sqr(v*x)) return true; ///此位移下和速度最大的情况比较return false;
}
int main()
{//freopen(&#","r",stdin);while(cin>>x1>>y1>>x2>>y2){cin>>v>>t;cin>>vx>>vy>>wx>>wy;double s=0;double mid,le=0,re=1e10;while(s<1e6) ///二分时间{mid=(le+re)/2;if(judge(mid)) re=mid; ///注意！else le=mid;s++;}printf("%.18fn",le);}return 0;
}