Cod sursă (job #294398)

#include <cstdio>
#include <algorithm>
#define X first
#define Y second
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.X-a.X, y1=b.Y-a.Y;
    int x2=d.X-c.X, y2=d.Y-c.Y;
    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.X.X*b.X.Y!=1LL*a.X.Y*b.X.X) return (1LL*a.X.X*b.X.Y)<(1LL*a.X.Y*b.X.X);
    if(a.Y*b.Y==0) return a.Y<b.Y;
    return a.X.X>b.X.X;
}
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].X.X, &p[i].X.Y);
    for(int i=1; i<=m; ++i)
    {
        sol[i]=inf;
        p[i+n].Y=i;
        scanf("%d%d", &p[i+n].X.X, &p[i+n].X.Y);
    }
    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].Y!=0)
        {
            while(st0>1 && largerSlope(p[st[st0-1]].X, p[st[st0]].X, zero, p[i].X)) --st0;
            sol[p[i].Y]=p[st[st0]].X.Y-(double)p[i].X.Y/p[i].X.X*p[st[st0]].X.X;
        }
        else
        {
            while(st0>0 && p[st[st0]].X.X>=p[i].X.X) --st0;
            while(st0>1 && largerSlope(p[st[st0-1]].X, p[st[st0]].X, p[st[st0]].X, p[i].X)) --st0;
            st[++st0]=i;
        }
    }
    for(int i=1; i<=m; ++i)
        printf("%.5lf\n", sol[i]);
    return 0;
}