Points (Convex Hull)

Andrew's Monotone Chain Algorithm Sort all points lexicographically by (x, y). Lower hull: Scan left to right. Maintain a stack. For each new point, while the last two stack points and the new point make a non-left tu...

Updated May 21, 2026

Track IOI

Year 1992

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Given $n$ points in the 2D plane, compute the convex hull --- the smallest convex polygon containing all the points. Output the hull vertices in order and compute the enclosed area.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution

Andrew's Monotone Chain Algorithm

Sort all points lexicographically by $(x, y)$.
Lower hull: Scan left to right. Maintain a stack. For each new point, while the last two stack points and the new point make a non-left turn, pop the stack. Push the new point.
Upper hull: Scan right to left with the same procedure.
Concatenate: Join the two hulls, removing the duplicate endpoints.

Turn Direction via Cross Product

For three points $P_1, P_2, P_3$, define: \[ \text{cross}(P_1, P_2, P_3) = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1). \]

$> 0$: left turn (counter-clockwise).
$= 0$: collinear.
$< 0$: right turn (clockwise).
To build the hull excluding collinear boundary points, pop when $\text{cross} \le 0$.

Area via Shoelace Formula

For hull vertices $P_0, P_1, \ldots, P_{m-1}$ in order: \[ \text{Area} = \frac{1}{2} \left| \sum_{i=0}^{m-1} (x_i \, y_{i+1} - x_{i+1} \, y_i) \right| \] where indices are taken modulo $m$. Using integer coordinates, $2 \times \text{Area}$ is always an integer, so the area is either an integer or a half-integer.

Complexity Analysis

Time: $O(n \log n)$ dominated by sorting. The hull construction is $O(n)$ amortized (each point is pushed and popped at most once).
Space: $O(n)$.

Example

Input:
8
0 0  1 0  2 1  2 3  1 4  0 3  -1 2  -1 1

Convex hull (CCW): (-1,1) (0,0) (1,0) (2,1) (2,3) (1,4) (0,3) (-1,2)

All 8 points lie on the convex hull in this case.

Notes

Using long long for coordinates and cross products avoids floating-point errors entirely.
Duplicate points are removed before processing.
Andrew's algorithm is preferred over Graham scan for its simplicity: no need to find a pivot point or handle angular sorting.
The Shoelace formula gives the signed area (positive for CCW ordering), so we take the absolute value.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1992 - Problem 1: Points (Convex Hull)
// Andrew's monotone chain algorithm. O(n log n)
// Outputs hull vertices in CCW order and computes area via Shoelace formula.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point {
    ll x, y;
    bool operator<(const Point& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
    bool operator==(const Point& o) const {
        return x == o.x && y == o.y;
    }
};

ll cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<Point> convexHull(vector<Point> pts) {
    int n = (int)pts.size();
    if (n < 2) return pts;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    n = (int)pts.size();
    if (n < 2) return pts;

    vector<Point> hull;

    // Lower hull
    for (int i = 0; i < n; i++) {
        while ((int)hull.size() >= 2 &&
               cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }

    // Upper hull
    int lower_size = (int)hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while ((int)hull.size() > lower_size &&
               cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }

    hull.pop_back(); // remove duplicate of first point
    return hull;
}

int main() {
    int n;
    scanf("%d", &n);

    vector<Point> pts(n);
    for (int i = 0; i < n; i++)
        scanf("%lld%lld", &pts[i].x, &pts[i].y);

    vector<Point> hull = convexHull(pts);

    printf("%d\n", (int)hull.size());
    for (auto& p : hull)
        printf("%lld %lld\n", p.x, p.y);

    // Compute area via Shoelace formula (2 * area to stay integer)
    ll area2 = 0;
    int m = (int)hull.size();
    for (int i = 0; i < m; i++) {
        int j = (i + 1) % m;
        area2 += hull[i].x * hull[j].y;
        area2 -= hull[j].x * hull[i].y;
    }
    if (area2 < 0) area2 = -area2;

    printf("Area = %lld", area2 / 2);
    if (area2 % 2) printf(".5");
    printf("\n");
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1992/points/solution.texC++ implementationcompetitive_programming/ioi/1992/points/solution.cpp