Cod sursă (job #143674)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

struct Point {
    int x, y;
    int ind;
    Point(int _x, int _y, int _ind) {
        x = _x; y = _y;
        ind = _ind;
    }
    Point() {
        x = y = ind = 0;
    }
    bool operator < (const Point &other) const {
        if ( 1LL * x * other.y != 1LL * other.x * y ) {
            return 1LL * x * other.y < 1LL * other.x * y;
        }
        if (ind * other.ind == 0) {
            return ind < other.ind;
        }
        return x < other.x;
    }
};
inline long long cross_product(const Point& A, const Point& B, const Point& C) {
    return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}
inline bool can_eliminate(const Point& A, const Point& B, const Point& C) {
    if (B.x == A.x) {
        return 1;
    }
    return (B.y - A.y) / (B.x - A.x) < (C.y / C.x);
}
int main() {

    ifstream cin("ydist.in");
    ofstream cout("ydist.out");

    int N, M; cin >> N >> M;

    vector <Point> P(N + M);

    for (int i = 0; i < N; ++i) {
        cin >> P[i].x >> P[i].y;
    }

    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        P[i + N].x = x;
        P[i + N].y = y;
        P[i + N].ind = i + 1;
    }
    sort(P.begin(), P.end(), less<Point>());

    vector <Point> stack(N+2);
    vector <double> sol(M+2, 1LL<<40);

    int SizeStack = 0;
    cout << setprecision(15);
    for (int i = 0; i < N + M; ++i) {
        if (P[i].ind == 0) {
            //must do convex hull
            while(SizeStack > 1 && cross_product(stack[SizeStack - 1], stack[SizeStack], P[i]) < 0) {
                --SizeStack;
            }
            stack[++SizeStack] = P[i];
        } else {

            while(SizeStack > 1 && can_eliminate(stack[SizeStack - 1], stack[SizeStack], P[i])) {
                --SizeStack;
            }

            for (int w = 1, j = SizeStack; j >= max(1, SizeStack-200); --j, w++) {
                double temp = stack[j].y - (double) P[i].y / P[i].x * stack[j].x;
                if (sol[P[i].ind] > temp) {
                    sol[P[i].ind] = temp;
                }
                sol[P[i].ind] =min(sol[P[i].ind], stack[w].y - (double) P[i].y / P[i].x * stack[w].x);
            }
        }
    }

    double mx = 0;
    for (int i = 1; i <= M; ++i) {
        cout << sol[i] << "\n";
        mx = max(mx, sol[i]);
    }
    cerr << mx << "\n";
    return 0;
}