ZR#317.【18 提高 2】A(计算几何 二分)

题意

Sol

非常好的一道题，幸亏这场比赛我没打，不然我估计要死在这个题上qwq

到不是说有多难，关键是细节太多了，我和wcz口胡了一下我的思路，然后他写了一晚上没调出来qwq

解法挺套路的，先提出一个$x$

然后维护一堆直线对应的上凸壳

在凸壳上二分即可。

由于这题的$x$很小，直接处理出答案就行了

/*

*/

#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 + , INF = 1e9 + , mod = 1e9 + , BB = ;

const double eps = 1e-;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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 = , t2 = , ans[MAXN];

double cross(Node x, Node y) {

//    printf("%lf\n", 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 + , P + N + );

    s1[++t1] = P[];

    for(int i = ; i <= N; i++) {

        if(t1 && P[i].a == s1[t1].a) t1--;

        while(t1 >  && cross(P[i], s1[t1]) <= cross(s1[t1], s1[t1 - ])) t1--;

        s1[++t1] = P[i];

    }

    for(int i = ; i <= N; i++) P[i].b = -P[i].b;

    sort(P + , P + N + );

    s2[++t2] = P[];

    for(int i = ; i <= N; i++) {

        if(t1 && P[i].a == s2[t2].a) t2--;

        while(t2 >  && cross(P[i], s2[t2]) <= cross(s2[t2], s2[t2 - ])) t2--;

        s2[++t2] = P[i];

    }

}

int Query(Node p, int x) {

    return p.a * x * x + p.b * x;

}

void MakeAns() {

    for(int i = , c = ; i <= BB; i++) {

        //printf("%lf\n", cross(s1[c], s1[c + 1]));

        while(c < t1 && cross(s1[c], s1[c + ]) <= (double)i) c++;

        ans[i + BB] = Query(s1[c], i);

    }

    for(int i = , c = ; i <= BB; i++) {

        while(c < t2 && cross(s2[c], s2[c + ]) <= (double)i) c++;

        ans[BB - i] = Query(s2[c], i);

    }

}

main() {

//    freopen("a.in", "r", stdin);

    N = read(); int Q = read();

    for(int i = ; i <= N; i++) P[i].a = read(), P[i].b = read();

    Get();

    MakeAns();

    while(Q--) {

        int x = read();

        printf("%lld\n", ans[x + BB]);

    }

    return ;

}

/*

2 2 1

1 1

2 1 1

*/