Not Frequent
0/10

# Convex Hull Trick

Author: Andi Qu

### Prerequisites

A way to find the maximum or minimum value of several convex functions at given points.

We wish to solve problems that are of the following form:

Consider a set of functions $\{f_i(x)\}$ on some range $[l,r]$ such that for any two functions $f_i$ and $f_j$, there exists some $m$ such that

• For all $x \in [l,m]$, $f_i(x)\le f_j(x)$
• For all $x \in [m,r]$, $f_i(x)\ge f_j(x)$

Answer queries of the form "what is the maximum/minimum $f_i(x)$ for some given $x\in [l,r]$," given that we have a way of finding $m$ efficiently.

A sufficient (but not necessary) set of conditions:

• All the functions are continuous along the range $[l,r]$.
• No two functions intersect at more than one point.

The most common case is where each $f_i(x)$ is of the form $a_ix+b_i$. Given two lines $f_i(x)=a_ix+b_i$ and $f_j(x)=a_jx+b_j$ such that $a_i, their intersection point at $m=\frac{b_i-b_j}{a_j-a_i}$ can be found in $O(1)$ time. Then it's clear that

• For all $x\le m$, $f_i(x)\ge f_j(x)$.
• For all $x\ge m$, $f_i(x)\le f_j(x)$.

The linear case is known as the convex hull trick because $\max_i(f_i(x))$ as a function of $x$ is concave up (similarly, $\min_i(f_i(x))$ as a function of $x$ is concave down). Check the images from the CF tutorial below if you don't know what this means.

Some possible nonlinear forms of $f_i(x)$:

• $f_i(x)=x^2+a_ix+b_i$
• Reduces to the linear case, since we can ignore the $x^2$ term when comparing two functions.
• $f_i(x) = \sqrt{x - a_i} + b_i$
• If this function is defined for all $x\in [l,r]$.
• Note that when $a_i, $\sqrt{x-a_i}-\sqrt{x-a_j}$ is strictly decreasing over the range $x\in [a_j,\infty)$.

In this module, we'll focus on the special case of CHT where "slopes" of functions are monotonic. This specific case is solvable in $O(N)$ using a std::deque in C++. For the more general $O(N \log N)$ CHT (which involves a std::set), see the LineContainer module.

Focus Problem – read through this problem before continuing!

## Tutorial

Resources
CFsolves problem above
GCP
Jeffrey Xiao

## Solution - The Fair Nut and Rectangles

I won't analyse this problem in great detail since the Codeforces blog in the resources already does so, but essentially, we sort the rectangles by $x$-coordinate and get the following DP recurrence:

$dp[i] = p_i \cdot q_i - a_i + \max_{j < i}(-p_j \cdot q_i + dp[j])$

Notice how the $-p_j \cdot q_i + dp[j]$ part of the recurrence describes a straight line $y = mx + c$.

Since we sorted the rectangles and no two rectangles are nested, the slopes of the lines we insert are strictly increasing. The query positions are also strictly increasing.

This means we can solve this problem using CHT in $O(N)$ time! Here is my implementation:

1#include <bits/stdc++.h>2typedef long long ll;3using namespace std;4
5struct Rect {6    ll x, y, a;7    bool operator<(Rect B) { return x < B.x; }8};9
10Rect a;

## Problems

StatusSourceProblem NameDifficultyTagsSolution
APIOEasy
Show Tags

DP, convex

External Sol
CEOIEasy
Show Tags

DP, convex

View Solution
IOINormal
Show Tags

DP, convex

External Sol
APIONormal
Show Tags

DP, convex

POINormal
Show Tags

DP, convex

POINormal
Show Tags

DP, convex

View Solution
PlatNormal
Show Tags

DP, convex

PlatNormal
Show Tags

convex

External Sol
JOIHard
Show Tags

DP, convex

View Solution