Convex Hull

C++

The Graham Scan algorithm works in 3 steps. First, it sorts all of the $n$ points by their counterclockwise angle around a pivot $P_0$, breaking ties by distance. This algorithm uses the leftmost (and bottommost if there is a tie), point as $P_0$.

We maintain a stack containing the points such that the following invariant holds: every three consecutive points $a,b,c$ of the stack form a counterclockwise turn. In other words, $c$ lies to the left of the line from $a$ to $b$. This condition implies that the points of the stack form the vertices of a convex polygon.

To start the creation of the convex hull, we choose 2 points. The pivot (first point), and the second point based on our initial sorting. After that, we attempt to add each point in $\texttt{cand}$ to the stack.

Denote our stack as $\texttt{hull}$, the top element of $\texttt{hull}$ as $\texttt{hull}[i]$ and $\texttt{cand}[j]$ as the $j$-th sorted candidate point. Before adding $\texttt{cand}[j]$ to the stack, we check whether $\texttt{hull}[i-1] \rightarrow \texttt{hull}[i] \rightarrow \texttt{cand}[j]$ forms a counterclockwise turn.

• If so, then we add $\texttt{cand}[j]$ to the stack and the invariant holds. Continue with $\texttt{cand}[j+1]$.
• Otherwise, $\texttt{hull}[i]$ lies within the convex hull of the other points in the stack along with $\texttt{cand}[j]$, so we pop $\texttt{hull}[i]$ from the stack and continue with $\texttt{cand}[j]$.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORE(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define trav(a, x) for (auto &a : x)

#define f first