Convex Hull Trick

#include<bits/stdc++.h>
#define ll long long

/// NOTE:
//      This is MIN-optimizing 
struct ConvexHullTrick 
{
    
    struct Line {
        int id;
        ll a, b;
        double control_min; // control_min
        
        Line(ll _1, ll _2, ll _3, double _4) {
            id = _1;
            a = _2; b = _3;
            control_min = _4;
        }
        
        // to change to MAX-optimizer, change ONLY this method:
        // replace the 2 '>' to '<'
        bool operator < (Line l) const {
            if (a != l.a)
                return a > l.a;
            return b > l.b;
        }
    };
    
    ll inf;
    vector<Line> lines;
    set<Line> bag;
    set<pair<double, int> > result;
    
    ConvexHullTrick() {
        inf = 1000000009ll * 1000000009ll;
    }
    
    void init() {
        lines.clear();
        bag.clear();
        result.clear();
    }
    
    double get_x_intersect(Line l1, Line l2) {
        return 1. * (l1.b - l2.b) / (l2.a - l1.a);
    }
    
    void addLine(ll a, ll b) { // add line y = ax + b
        
        Line line(lines.size(), a, b, -inf);
        lines.push_back(line);
        
        // the first line
        if (bag.empty()) {
            bag.insert(line);
            result.insert({-inf, line.id});
            return;
        }
        
        // if bag contains a line with the same slope and smaller-or-equal intercept
        // or if line is useless
        auto it = bag.lower_bound(line);
        if (it->a == line.a)
            return;
        if (it != bag.begin() && it != bag.end()) {
            auto before = it; before--;
            if (get_x_intersect(*before, *it) <= get_x_intersect(*before, line))
                return;
        }
        
        // normal case: line is useful
        //      first: remove forward-useless lines
        if (it != bag.begin()) {
            it--;
            while(it != bag.begin()) {
                auto before = it; before--;
                
                if (get_x_intersect(*before, line) <= get_x_intersect(*before, *it)) {
                    result.erase({it->control_min, it->id});
                    bag.erase(it);
                    it = before;
                }
                else
                    break;
            }
            
            line.control_min = get_x_intersect(line, *it);
        }
        else {
            line.control_min = -inf;
        }
        //      second: add line
        result.insert({line.control_min, line.id});         
        auto line_it = bag.insert(line).first;
        //      third: remove backward-useless lines
        it = line_it; it++;
        while(it != bag.end()) {
            auto next = it; next++;
            if (next == bag.end()) break;
            
            if (get_x_intersect(line, *next) <= get_x_intersect(line, *it)) {
                Line lnext = *next;
                lnext.control_min = get_x_intersect(line, *next);
                
                result.erase({next->control_min, next->id});
                result.insert({lnext.control_min, lnext.id});
                bag.erase(next);
                bag.insert(lnext);
                
                result.erase({it->control_min, it-> id});
                it = bag.erase(it);
                
            }
            else
                break;
        }
        
        // update the line to the right of current line
        if (it != bag.end()) {
            Line lit = *it;
            lit.control_min = get_x_intersect(line, lit);
            
            result.erase({it->control_min, it->id});
            result.insert({lit.control_min, lit.id});
            
            bag.erase(it);
            bag.insert(lit);
        }
        
        
    }
    
    pair<ll, int> query(ll x) {
        auto it = result.upper_bound({x, -1});
        it--;
        
        ll best_value = 1ll * lines[it->second].a * x + lines[it->second].b;
        return {best_value, it->second}; // {best value, index of the best line}
    }
    
};