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.
O(n) since there are n lines and only n lines can be added or removed.
O(log n) due to the use of binary search.
// 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]);
}
}
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.)
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);
}
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)
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);
}
}
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]];
}
#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;
}