Cod sursă (job #143671)

#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <algorithm>
//#include <iomanip>

#define f first
#define s second
#define mp make_pair
using namespace std;
double eps = 1e-9;
const double inf = 1e7;
const int K_BACK = 100;

vector<pair<int, int> > q;

inline double panta(pair<int, int> A) {
    return (A.s + 0.0) / A.f;
}

inline bool cmp(pair<int, int> A, pair<int, int> B) {
    return panta(A) > panta(B);
}

inline bool cmp2(int a, int b) {
    pair<int, int> A = q[a], B = q[b];
    return cmp(A, B);
}

int comp(double a, double b) {
    if(fabs(a - b) < eps)
        return 0;
    if(a < b)
        return - 1;
    return 1;
}

int main() {

    ifstream cin("rafaela2.in");
    ofstream cout("rafaela2.out");
    
    int n, m; cin >> n >> m;
    
    vector<pair<int, int> > p(n);
    q = vector<pair<int, int> > (m);

    vector<int> poz;
    vector<double> ans(m, 0.0);

    for(int i = 0; i < n; ++i) 
        cin >> p[i].f >> p[i].s;
        
    for(int i = 0; i < m; ++i) {
        cin >> q[i].f >> q[i].s;
        poz.push_back(i);
    }

    sort(p.begin(), p.end(), cmp);
    sort(poz.begin(), poz.end(), cmp2);
    
    int ite = 0;

    for(int i = 0; i < m; ++i) { 
        pair<int, int> now = q[poz[i]];
        long double now_slope = panta(now);
        
        long double tmp = inf;
        int new_ite = 0;

        for(int j = max(0, ite - K_BACK); j < min(n, ite + K_BACK); ++j) {
            if(p[j].s - now_slope * p[j].f < 0)
                break;

            if(tmp > p[j].s - now_slope * p[j].f) {
                tmp = min(tmp, p[j].s - now_slope * p[j].f);
                new_ite = j;
            }
        }
        
        ite = new_ite;
        ans[poz[i]] = tmp;
    }
    
    cout.precision(15);

    for(int i = 0; i < m; ++i)
        cout << ans[i] << "\n";
}