Convex Hull

struct point{
    ll x, y;
    point(){}
    point(ll _x, ll _y ){
        x = _x;
        y = _y;
    }
};

deque<point> H;

ll cross(point a, point b, point c){
    return (b.x - a.x) * (c.y - a.y) -
           (c.x - a.x) * (b.y - a.y);
}

ll eval(point p, int x){
    return p.x * x + p.y;
}

void hull_add(point p) {
    while(H.size() > 1 && cross(H[H.size() - 2], H[H.size() - 1], p) >= 0) H.pop_back();
    H.push_back(p);
}

ll hull_query(int x) {
    while(H.size() > 1 and eval(H[0], x) >= eval(H[1], x)) H.pop_front();
    return eval(H[0], x);
}