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("1.txt","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("%.18f\n",le);
    }
    return 0;
}