c/c++语言开发共享ZR#317.【18 提高 2】A(计算几何 二分)

/*    */  #include<iostream>  #include<cstdio>  #include<cstring>  #include<algorithm>  #include<map>  #include<vector>  #include<set>  #include<queue>  #include<cmath>  //#include<ext/pb_ds/assoc_container.hpp>  //#include<ext/pb_ds/hash_policy.hpp>  #define pair pair<int, int>  #define mp(x, y) make_pair(x, y)  #define fi first  #define se second  #define int long long   #define ll long long   #define ull unsigned long long   #define rg register   #define pt(x) printf("%d ", x);  //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++)  //char buf[(1 << 22)], *p1 = buf, *p2 = buf;  //char obuf[1<<24], *o = obuf;  //void print(int x) {if(x > 9) print(x / 10); *o++ = x % 10 + '0';}  //#define os  *o++ = ' ';  using namespace std;  //using namespace __gnu_pbds;  const int maxn = 1e6 + 10, inf = 1e9 + 10, mod = 1e9 + 7, bb = 32323;  const double eps = 1e-9;  inline int read() {      char c = getchar(); int x = 0, f = 1;      while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}      while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();      return x * f;  }  int n;  struct node {      double a, b;      bool operator < (const node &rhs) const {          return a == rhs.a ? b < rhs.b : a < rhs.a;      }  }p[maxn], s1[maxn], s2[maxn];  int t1 = 0, t2 = 0, ans[maxn];  double cross(node x, node y) {  //    printf("%lfn", 1.0 * (y.b - x.b) / (x.a - x.b));      return 1.0 * (y.b - x.b) / (x.a - y.a);  }  void get() {      sort(p + 1, p + n + 1);      s1[++t1] = p[1];      for(int i = 2; i <= n; i++) {          if(t1 && p[i].a == s1[t1].a) t1--;          while(t1 > 1 && cross(p[i], s1[t1]) <= cross(s1[t1], s1[t1 - 1])) t1--;          s1[++t1] = p[i];      }      for(int i = 1; i <= n; i++) p[i].b = -p[i].b;      sort(p + 1, p + n + 1);      s2[++t2] = p[1];      for(int i = 2; i <= n; i++) {          if(t1 && p[i].a == s2[t2].a) t2--;          while(t2 > 1 && cross(p[i], s2[t2]) <= cross(s2[t2], s2[t2 - 1])) t2--;          s2[++t2] = p[i];      }  }  int query(node p, int x) {      return p.a * x * x + p.b * x;  }  void makeans() {      for(int i = 1, c = 1; i <= bb; i++) {          //printf("%lfn", cross(s1[c], s1[c + 1]));          while(c < t1 && cross(s1[c], s1[c + 1]) <= (double)i) c++;          ans[i + bb] = query(s1[c], i);      }      for(int i = 1, c = 1; i <= bb; i++) {          while(c < t2 && cross(s2[c], s2[c + 1]) <= (double)i) c++;          ans[bb - i] = query(s2[c], i);      }  }  main() {  //    freopen("a.in", "r", stdin);      n = read(); int q = read();      for(int i = 1; i <= n; i++) p[i].a = read(), p[i].b = read();      get();      makeans();      while(q--) {          int x = read();          printf("%lldn", ans[x + bb]);      }      return 0;  }  /*  2 2 1  1 1  2 1 1  */