The Meeting Place Cannot Be Changed

QUESTION

The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.\n\nAt some points on the road there are n friends, and i-th of them is standing at the point xi meters and can move with any speed no greater than vi meters per second in any of the two directions along the road: south or north.\n\nYou are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn’t need to have integer coordinate.\nInput\n\nThe first line contains single integer n (2n60000) the number of friends.\n\nThe second line contains n integers x1,x2,…,xn (1xi109) the current coordinates of the friends, in meters.\n\nThe third line contains n integers v1,v2,…,vn (1vi109) the maximum speeds of the friends, in meters per second.\nOutput\n\nPrint the minimum time (in seconds) needed for all the n friends to meet at some point on the road.\n\nYour answer will be considered correct, if its absolute or relative error isn’t greater than 10-6. Formally, let your answer be a, while jury’s answer be b. Your answer will be considered correct if holds.

“TESTCASE_1”: “3\n7 1 3 \n1 2 1\n###—###SEPERATOR—###—\n2.000000”, “TESTCASE_2”: “2\n4 5\n10 8\n###—###SEPERATOR—###—\n0.055556”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “4\n5 10 3 2\n2 3 2 4\n###—###SEPERATOR—###—\n1.400000”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>  
#include <cstdio>  
#include <cmath>  
#include <iomanip>  
using namespace std;  
typedef long long LL;  
const int MAXN = 1e6 + 8;  
const double EPS = 1e-6;  
  
int n, x[MAXN], v[MAXN];  
inline double getsum(double mid)  
{  
    double res = 0;  
    for(int i = 0; i < n; i++){  
        res = max(res, fabs(mid - x[i]) / v[i]);  
    }  
    return res;  
}  
  
int main()  
{  
    #ifdef LOCAL  
    freopen("b.txt", "r", stdin);  
    //freopen("b.out", "w", stdout);  
    int T = 4;  
    while(T--){  
    #endif // LOCAL  
    ios::sync_with_stdio(false); cin.tie(0);  
  
    int i;  
    double l = 1e9 + 8, r = 0, ll, rr, ans = 0, ans1, ans2;  
    cin >> n;  
    for(i = 0; i < n; i++){  
        cin >> x[i];  
        l = min(l, (double)x[i]);  
        r = max(r, (double)x[i]);  
    }  
    for(i = 0; i < n; i++) cin >> v[i];  
    ans = min(getsum(l), getsum(r)); //答案一般不会取到边界,但有时候可能可以  
    while(l + EPS < r){  
        ll = l + (r - l) / 3;  
        rr = r - (r - l) / 3;  
        ans1 = getsum(ll);  
        ans2 = getsum(rr);  
        if(ans1 > ans2){  
            l = ll;  
        }  
        else r = rr;  
        ans = min(ans, min(ans1, ans2));  
    }  
    cout << fixed << setprecision(6) << ans << endl;  
  
  
    #ifdef LOCAL  
    cout << endl;  
    }  
    #endif // LOCAL  
    return 0;  
}  
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.