USACO银牌题目 TheMeetingPlaceCannotBeChanged（二分查找) 样例代码

#include <bits/stdc++.h>

using namespace std;

int n;

const int MAXF=6e4;

vector<int> x(MAXF+1),v(MAXF+1);

bool is_larger_eq_min(double m){

    //最大的起点小于等于最小终点=>存在地点所有客人都能到=>m大于等于最小时间

    double maxa=x[1]-m*v[1];

    double minb=x[1]+m*v[1];

    for(int i=2;i<=n;i++){

        maxa=max(x[i]-m*v[i],maxa);

        minb=min(x[i]+m*v[i],minb);

        if(maxa>minb){

            return false;

        }

    }

    return true;

}    

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>x[i];

    }    

    for(int i=1;i<=n;i++){

        cin>>v[i];

    }

    double l=0, r=1e9+1;

    while(r-l>1e-7){

        double m=(r+l)/2;

        if(is_larger_eq_min(m)){

            r=m;

        }else{

            l=m;

        }    

    }  

    cout<<setprecision(8)<<r<<endl;//必须设置,否则输出精度可能不够题目要求

    return 0;

}