CodeForces - 782B

一、问题介绍

二、题解

此题的关键在于采用了二分法后，理解相遇时间取决于抵达时间最晚的那个人，以此为基准不断进行二分。其余的知识点就是精度的把控，比如1e-6在浮点类型的比较中的使用。

三、实现代码

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int main()
{
    int n,i;
    double *person,*speed,max_pos,min_pos,right_min_speed,left_min_speed,mid,distance,tmp;
    while(cin>>n){
        max_pos=0;
        left_min_speed=0;
        min_pos=10e9;
        right_min_speed=0;
        person=new double[n];
        speed=new double[n];
        for(i=0;i<n;i++){
            cin>>person[i];
            if(max_pos<person[i])max_pos=person[i];
            if(min_pos>person[i])min_pos=person[i];
        }
        for(i=0;i<n;i++){
            cin>>speed[i];
        }

        while(max_pos-min_pos>1e-12){
            mid=(max_pos+min_pos)/2;
            right_min_speed=0;
            left_min_speed=0;
            for(i=0;i<n;i++){
                distance=fabs(person[i]-mid);
                if(person[i]-mid>0){
                    tmp=distance/speed[i];
                    if(tmp>right_min_speed) right_min_speed=tmp;
                }
                else{
                    tmp=distance/speed[i];
                    if(tmp>left_min_speed) left_min_speed=tmp;
                }
            }
            if(right_min_speed>left_min_speed) min_pos=mid;
            else max_pos=mid;
        }
        if(right_min_speed>left_min_speed) cout<<fixed<<setprecision(12)<<right_min_speed<<endl;
        else cout<<fixed<<setprecision(12)<<left_min_speed<<endl;
    }
    return 0;
}