Convex Hull Trick for Line Queries

📌 Table of Contents

1. Problem

Given a set of linear functions in the form f(x) = ax + b and a series of query points x, determine the maximum or minimum value of f(x) for each query.

2. Create the CHT structure


// Convex Hull Trick structure
struct CHT
{
  int n,a[maxn],b[maxn];
  vector <int> line;
  vector <ld> point;
  CHT()
  {
	//constructor
    point.pp(-1e18);
  }

  ld intersect (int x, int y)
  {
    //calculate intersect of 2 lines
    return (ld)1.0 * (b[x]-b[y])/(a[y]-a[x]);
  }
}
        

3. Build function

For the maximum-value problem, sort the lines by their slope in ascending order. This ensures that the maximum values of ax + b at any x will lie on the upper convex hull. (For the minimum-value problem, simply sort in descending order instead.)

Convex vs Concave
On the left is the max convex hull function, on the right is the min convex hull.
Convex vs Concave

void build()
{
  vector <int> id;
  for(int i=1;i<=n;++i)   id.pp(i);
  sort(all(id),[&](const int& x, const int& y){
    return a[x]<a[y];});
  for(int i:id)   add(i);
}
        

4. Add function

Case 1: Slope coefficients are equal a → Remove edges based on b

Case 2: Slope coefficients are different a (applies to both types of Convex Hull)

Convex vs Concave

void add(int i)
{
  while(line.size()>0)
  {
    if(a[line.back()]==a[i])
    {
      if(b[line.back()]>=b[i])    break;
      else
      {
        line.pop_back();
        if(line.size()>0)   point.pop_back();
      }
    }
    else
    {
      if(line.size()<2)   break;
      if(intersect(i,line.back())<intersect(i,line[line.size()-2]))
      {
        line.pop_back();
        if(line.size()>0)   point.pop_back();
      }
      else    break;
    }
  }
  if(line.size()==0 or a[line.back()]!=a[i])
  {
      if(line.size()>0)   point.pp(intersect(line.back(),i));
      line.pp(i);
  }
}
        

5. Get function

When we have x , the remaining task is to perform binary search on the point vector and print the result


ll gt(ll x)
{
  int id=upper_bound(all(point),x)-point.begin()-1;
  return a[line[id]]*x+b[line[id]];
}
        

6. Template


#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using pld = pair <ld,ld>;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e5+5, mod = 1e9+7;

struct CHT
{
  int n,a[maxn],b[maxn];
  vector <int> line;
  vector <ld> point;

  CHT(){
    point.pp(-1e18);}

    ld intersect (int x, int y){
      return (ld)1.0 * (b[x]-b[y])/(a[y]-a[x]);}

    void add(int i)
    {
      while(line.size()>0)
      {
        if(a[line.back()]==a[i])
        {
          if(b[line.back()]>=b[i])    break;
          else
          {
            line.pop_back();
            if(line.size()>0)   point.pop_back();
          }
        }
        else
        {
          if(line.size()<2)   break;
          if(intersect(i,line.back())<intersect(i,line[line.size()-2]))
          {
            line.pop_back();
            if(line.size()>0)   point.pop_back();
          }
          else    break;
          }
        }
        if(line.size()==0 or a[line.back()]!=a[i])
        {
            if(line.size()>0)   point.pp(intersect(line.back(),i));
            line.pp(i);
        }
    }

    void build()
    {
      vector <int> id;
      for(int i=1;i<=n;++i)   id.pp(i);
      sort(all(id),[&](const int& x, const int& y){
        return a[x]<a[y];});
      for(int i:id)   add(i);
    }

    ll gt(ll x)
    {
      int id=upper_bound(all(point),x)-point.begin()-1;
      return a[line[id]]*x+b[line[id]];
    }

};
CHT f;


void input()
{
  cin>>f.n;
  for(int i=1;i<=f.n;++i)   cin>>f.a[i]>>f.b[i];
  f.build();
  int m;
  cin>>m;
  while(m-->0)
  {
    ll x;
    cin>>x;
    cout<<f.gt(x)<<el;
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  return 0;
}
        

7. Problem set