convex hull trick

struct convex_hull_trick {
    ld inter(pair<ll, ll> a, pair<ll, ll> b) {
        return 1. * (b.second - a.second) / (a.first - b.first);
    }
    void add(ll k, ll b) {
        while (p.size() > 0 && p.back() * k + b < p.back() * l.back().first + l.back().second) {
            p.pop_back();
            l.pop_back();
        }
        if (l.size() == 0) {
            l.push_back({k, b});
            return;
        }
        if (l.back().first == k && l.back().second <= b)
            return;
        p.push_back(inter(l.back(), {k, b}));
        l.push_back({k, b});
    }
    ll get(ll x) {
        int id;
        if (p.size() == 0) id = 0;
        else id = lower_bound(p.begin(), p.end(), x) - p.begin();
        return l[id].first * x + l[id].second;
    }
};