Cod sursă (job #143669)

//O(N log N) - 100 de puncte. Distanta minima pe Oy pana la cel mai apropiat punct situat
//DEASUPRA dreptei

#include <cstdio>
#include <algorithm>

using namespace std;

#define maxn 100010
#define inf 1000000000

int n, m;
pair<pair<int, int>, int> p[2*maxn];
int st0, st[maxn];
double sol[maxn];

int largerSlope(pair<int, int> a, pair<int, int> b, pair<int, int> c, pair<int, int> d)
{
    int x1=b.first-a.first, y1=b.second-a.second;
    int x2=d.first-c.first, y2=d.second-c.second;

    return 1LL*y1*x2>=1LL*y2*x1;
}

inline int cmp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b)
{
    if(1LL*a.first.first*b.first.second!=1LL*a.first.second*b.first.first)
        return (1LL*a.first.first*b.first.second)<(1LL*a.first.second*b.first.first);
    if(a.second*b.second==0)
        return a.second<b.second;
    return a.first.first>b.first.first;
}

int main()
{
    freopen("ydist.in", "r", stdin);
    freopen("ydist.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(int i=1; i<=n; ++i)
        scanf("%d%d", &p[i].first.first, &p[i].first.second);

    for(int i=1; i<=m; ++i)
    {
        sol[i]=inf;
        p[i+n].second=i;
        scanf("%d%d", &p[i+n].first.first, &p[i+n].first.second);
    }

    n+=m;
    sort(p+1, p+n+1, cmp);

    pair<int, int> zero=make_pair(0, 0);

    for(int i=1; i<=n; ++i)
    {
        if(p[i].second!=0)
        {
            while(st0>1 && largerSlope(p[st[st0-1]].first, p[st[st0]].first, zero, p[i].first))
                --st0;

            sol[p[i].second]=p[st[st0]].first.second-(double)p[i].first.second/p[i].first.first*p[st[st0]].first.first;
        }
        else
        {
            while(st0>0 && p[st[st0]].first.first>=p[i].first.first)
                --st0;

            while(st0>1 && largerSlope(p[st[st0-1]].first, p[st[st0]].first, p[st[st0]].first, p[i].first))
                --st0;

            st[++st0]=i;
        }
    }

    for(int i=1; i<=m; ++i)
        printf("%.5lf\n", sol[i]);

    return 0;
}