Cod sursă (job #525012)

#include <fstream>
#include <algorithm>

using namespace std;

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

struct Point {
  int x, y, ind;
  bool operator < (const Point &other) const {
    if(1LL * x * other.y != 1LL * y * other.x)
      return 1LL * x * other.y < 1LL * y * other.x;
    if(other.y * y == 0)
      return y < other.y;
    return x > other.x;
  }
};

int n, m, vf;

Point v[200005];
double sol[100005];
int st[200005];

int det(int a, int b, int c, int d) {
  int x1 = v[b].x - v[a].x, y1 = v[b].y - v[a].y, x2 = v[d].x - v[c].x, y2 = v[d].y - v[c].y;
  return 1LL * y1 * x2 >= 1LL * x1 * y2;
}

int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
    cin >> v[i].x >> v[i].y;
  for(int i = 1; i <= m; i++)
    cin >> v[i + n].x >> v[i + n].y, v[i + n].ind = i;
  n += m;
  sort(v + 1, v + n + 1);
  for(int i = 1; i <= n; i++) {
    if(v[i].ind) {
      while(vf > 1 && det(st[vf - 1], st[vf], 0, i))
        vf--;
      sol[v[i].ind] = v[st[vf]].y - (double)v[i].y * v[st[vf]].x / v[i].x;
    } else {
      while(vf && v[st[vf]].x >= v[i].x)
        vf--;
      while(vf > 1 && det(st[vf - 1], st[vf], st[vf], i))
        vf--;
      st[++vf] = i;
    }
  }
  for(int i = 1; i <= m; i++)
    cout << sol[i] << "\n";
  return 0;
}