# 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;
}
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}
}

};
```