1753 - Need for Speed

1753.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int, char> ic;

const int oo = ~(1<<31);
const double EPS = 1e-9;


bool check(double m, vi &d, vi &v, int t) {
    double st = 0.;

    for(int i=0; i<d.size(); i++) {
        st += d[i] / (v[i] + m);
    }

    return ((double)t - st) <= EPS;
}

int main() {

    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    cout.precision(9);

    int n, s;
    while(cin >> n >> s) {

        int mn = oo;
        vi d(n), v(n);
        for(int i=0; i<n; i++) {
            cin >> d[i] >> v[i];
            mn = min(mn, v[i]);
        }

        double hi = 1e9, lo = (-mn + 1e-6), m;
        for(int i=0; i<500; i++) {
            m = lo + (hi - lo) / 2.;
            if(check(m, d, v, s)) lo = m;
            else hi = m;
        }
        cout << fixed << lo << endl;
    }

    return 0;
}