IOI 1992 - Problem 1: Points (Convex Hull)

// 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;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage[margin=2.5cm]{geometry}
\usepackage{xcolor}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!50!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 1992 -- Problem 1: Points (Convex Hull)}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}

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.

\section{Solution}

\subsection{Andrew's Monotone Chain Algorithm}

\begin{enumerate}
  \item \textbf{Sort} all points lexicographically by $(x, y)$.
  \item \textbf{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.
  \item \textbf{Upper hull:} Scan right to left with the same procedure.
  \item \textbf{Concatenate:} Join the two hulls, removing the duplicate
    endpoints.
\end{enumerate}

\subsection{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).
\]
\begin{itemize}
  \item $> 0$: left turn (counter-clockwise).
  \item $= 0$: collinear.
  \item $< 0$: right turn (clockwise).
\end{itemize}

To build the hull excluding collinear boundary points, pop when
$\text{cross} \le 0$.

\subsection{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.

\section{Complexity Analysis}

\begin{itemize}
  \item \textbf{Time:} $O(n \log n)$ dominated by sorting. The hull
    construction is $O(n)$ amortized (each point is pushed and popped at
    most once).
  \item \textbf{Space:} $O(n)$.
\end{itemize}

\section{Implementation}

\begin{lstlisting}
#include <iostream>
#include <vector>
#include <algorithm>
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);
}

// Returns convex hull in CCW order.
// strict=true excludes collinear points on hull edges.
vector<Point> convexHull(vector<Point> pts, bool strict = true) {
    int n = pts.size();
    if (n < 2) return pts;

    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    n = pts.size();
    if (n < 2) return pts;

    vector<Point> hull;

    // Lower hull
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2) {
            ll c = cross(hull[hull.size()-2],
                         hull[hull.size()-1], pts[i]);
            if (strict ? c <= 0 : c < 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(pts[i]);
    }

    // Upper hull
    int lower_size = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while ((int)hull.size() > lower_size) {
            ll c = cross(hull[hull.size()-2],
                         hull[hull.size()-1], pts[i]);
            if (strict ? c <= 0 : c < 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(pts[i]);
    }

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

int main() {
    int n;
    cin >> n;

    vector<Point> pts(n);
    for (int i = 0; i < n; i++)
        cin >> pts[i].x >> pts[i].y;

    vector<Point> hull = convexHull(pts);

    cout << hull.size() << "\n";
    for (auto& p : hull)
        cout << p.x << " " << p.y << "\n";

    // Compute area using Shoelace formula
    ll area2 = 0;
    int m = 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;

    cout << "Area = " << area2 / 2;
    if (area2 % 2) cout << ".5";
    cout << "\n";

    return 0;
}
\end{lstlisting}

\section{Example}

\begin{verbatim}
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)
\end{verbatim}

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

\section{Notes}

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

\end{document}