SyntaxPilot
Courses/Competitive Programming/Lesson 80
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 80 of 90

Geometry 2: convex hull

queued

These are the notes for Competitive Programming episode 80. The convex hull of a set of points is the tightest fence around all of them: the smallest convex polygon that contains every point. Fence the Farm shows the brute force (every pair of trees as a possible side, checked against every tree: O(n³), TLE), then Andrew's monotone chain: sort the points, walk left to right keeping a stack and popping every corner that is not a left turn (the lower hull), then right to left (the upper hull): O(n log n). A real bug: popping only on cross < 0 keeps the tree (2,0) in the middle of a side (5 corners instead of 4). The Longest Pole (the farthest pair of points) uses the hull and rotating calipers, two pointers going round it in O(h). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Hammer nails into a board where the trees are, stretch a rubber band around all of them and let go: it snaps tight around the outside nails. That shape is the convex hull. Run your finger along the band counterclockwise from the leftmost nail: at every corner it bends the same way, left (episode 79's convex check). Building it nail by nail, if a new nail makes the band bend the wrong way at the previous nail, that nail was never a corner and the band lets it go (pop). A nail exactly on a straight stretch doesn't bend the band at all: it is not a corner either.

Problem H1 · Fence the Farm

(Written for this course.)

  • n ≤ 2·10^5 trees at distinct integer points, |x|, |y| ≤ 10^9.
  • Print the number of corners of the shortest fence enclosing every tree, then the corners counterclockwise, starting from the leftmost (lowest on a tie). A tree in the middle of a side is not a corner.
7
0 0
2 0
4 0
4 4
0 4
2 2
1 3

Expected: the square (0,0) (4,0) (4,4) (0,4); (2,0) is in the middle of the bottom side, (2,2) and (1,3) are inside.

Why convex? A dent can always be cut straight across, and a straight line is shorter, so the shortest fence has no dents.

Attempt 1: every pair as a fence side (TLE)

A pair i → j is a side if every other tree is on its left, or exactly between i and j.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    int sides = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {          // is i -> j a side of the fence?
            if (i == j) continue;
            bool ok = true;
            for (int k = 0; k < n && ok; k++) {
                ll c = cross(p[j] - p[i], p[k] - p[i]);
                if (c < 0) ok = false;                  // k is on the right: not a side
                if (c == 0 && k != i && k != j && !(min(p[i], p[j]) < p[k] && p[k] < max(p[i], p[j]))) ok = false;
            }
            sides += ok;
        }
    cout << sides << "\n";                          // one side per corner
}
4

Right, but O(n³) in the worst case: with 200000 random trees (mt19937 gen(80)) the SyntaxPilot compiler stops it with Time Limit Exceeded.

Andrew's monotone chain

  1. Sort the points by x, then by y; remove duplicates.
  2. Lower hull, left to right, with a stack: for each point, while the last two stack points and the new point are not a left turn (cross ≤ 0), pop; then push.
  3. Upper hull, right to left, the same way (stop popping at the lower hull's size t).
  4. The upper walk ends at the first point again: drop the last point (resize(k − 1)).

Each point is pushed once and popped at most once: the walks are O(n), the sort is O(n log n). The result is counterclockwise, starting from the smallest (x, y). (The Graham scan does the same with an angle sort.)

The collinear bug: < 0 instead of <= 0

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) < 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) < 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    vector<P> h = convexHull(p);
    cout << h.size() << "\n";
    for (auto& v : h) cout << v.x << " " << v.y << "\n";   // counterclockwise
}
5
0 0
2 0
4 0
4 4
0 4

(2,0) sits exactly on the bottom side: a straight turn (cross = 0) was not popped.

The fix: pop on <= 0 in both loops

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    vector<P> h = convexHull(p);
    cout << h.size() << "\n";
    for (auto& v : h) cout << v.x << " " << v.y << "\n";   // counterclockwise
}
4
0 0
4 0
4 4
0 4

Edge case: all trees on one line (the fence is a segment; (1,1) is dropped):

3
0 0
1 1
3 3
2
0 0
3 3

Edge case: one tree:

1
5 5

200000 random trees (only the number of corners is printed):

27

Random points have very few hull corners (about O(log n) in a square), but the code must also handle inputs where every point is a corner.

Problem H2 · The Longest Pole

(Written for this course.)

  • The same trees. Print the largest squared distance between two trees (so the answer is an integer).

Observation 1. Both ends of the farthest pair are hull corners: if an end were inside, sliding it outwards would make the pair longer.

Observation 2 (rotating calipers). For each side i → i + 1 of the hull, the corner j farthest from that side moves forward (counterclockwise) as the side moves forward. So two pointers go round the hull together: advance j while cross(h[i+1] − h[i], h[j+1] − h[j]) > 0 (the next corner is farther from the side), then check j against both ends of the side. Every pointer goes round once: O(h).

Attempt 1: every pair

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

ll dist2(P a, P b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }

int main() {
    mt19937 gen(80);
    int n = 200000;
    vector<P> p(n);
    for (auto& v : p) v = {(ll)(gen() % 1000000001), (ll)(gen() % 1000000001)};   // 200000 random trees
    ll best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) best = max(best, dist2(p[i], p[j]));   // every pair
    cout << best << "\n";
}

2·10^10 distance computations: Time Limit Exceeded in the SyntaxPilot compiler.

Hull + rotating calipers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

ll dist2(P a, P b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

ll farthest(const vector<P>& h) {                    // rotating calipers on a ccw hull
    int m = h.size();
    if (m == 1) return 0;
    if (m == 2) return dist2(h[0], h[1]);
    ll best = 0;
    for (int i = 0, j = 1; i < m; i++) {
        int ni = (i + 1) % m;
        while (cross(h[ni] - h[i], h[(j + 1) % m] - h[j]) > 0) j = (j + 1) % m;   // j: farthest from side i
        best = max({best, dist2(h[i], h[j]), dist2(h[ni], h[j])});
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    cout << farthest(convexHull(p)) << "\n";
}
6
0 0
5 1
6 4
2 6
-1 3
3 3
52

(0,0) and (6,4): 6² + 4² = 52. 200000 random trees:

1992369575050401428

About 2·10^18, close to the top of long long (the maximum possible is 8·10^18 < 9.22·10^18).

Stress test

Against every pair, on small grids (coordinates 0 … 6) with many ties and straight lines:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

ll dist2(P a, P b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

ll farthest(const vector<P>& h) {                    // rotating calipers on a ccw hull
    int m = h.size();
    if (m == 1) return 0;
    if (m == 2) return dist2(h[0], h[1]);
    ll best = 0;
    for (int i = 0, j = 1; i < m; i++) {
        int ni = (i + 1) % m;
        while (cross(h[ni] - h[i], h[(j + 1) % m] - h[j]) > 0) j = (j + 1) % m;   // j: farthest from side i
        best = max({best, dist2(h[i], h[j]), dist2(h[ni], h[j])});
    }
    return best;
}

int main() {
    mt19937 gen(80);
    for (int it = 1; it <= 500; it++) {
        int n = gen() % 12 + 1;
        vector<P> p(n);
        for (auto& v : p) v = {(ll)(gen() % 7), (ll)(gen() % 7)};   // small grid: many ties and lines
        ll slow = 0;
        for (auto& a : p) for (auto& b : p) slow = max(slow, dist2(a, b));
        if (slow != farthest(convexHull(p))) { cout << "mismatch on test " << it; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict for n = 2·10^5
every pair as a side, check every tree O(n³) TLE
farthest pair, every pair O(n²) = 2·10^10 TLE
sort the points O(n log n) ≈ 4·10^6 fast
monotone chain walks O(n) accepted
rotating calipers O(h) accepted

Memory: O(n). Squared distances up to 8·10^18: long long.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
pop only on cross < 0 5 corners, (2,0) included straight points stay pop on cross <= 0
no unique after sorting Wrong Answer / repeated corners zero-length sides sort + unique (needs operator==)
forgetting h.resize(k − 1) the first corner printed twice the upper walk ends there drop the last point
int for squared distances overflow up to 8·10^18 long long
upper loop pops into the lower hull corners lost k >= 2 instead of k >= t stop at t = k + 1
calipers on a hull with collinear points j can stall or skip ties in the comparison build the hull with <= 0

Mini project

Farm planner. Read the trees, print the fence corners, the fence length, twice the fenced area (episode 81's shoelace formula, exact), and the two trees farthest apart. Then add one new tree at a time and report whether the fence must change (is the tree outside the current hull?).

Practice

These are the homework problems from the episode.

1. The length of the fence. Sum the lengths of the hull's sides, wrapping round. With 2 corners the fence goes there and back.

Solution

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

int main() {                                        // the length of the fence
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    vector<P> h = convexHull(p);
    int m = h.size();
    double len = 0;
    for (int i = 0; i < m; i++) {                   // every side, wrapping round (2 corners: there and back)
        P d = h[(i + 1) % m] - h[i];
        len += sqrt((double)d.x * d.x + (double)d.y * d.y);
    }
    cout << fixed << setprecision(6) << len << "\n";
}
16.000000

The square farm has a 16 m fence.

2. Is a new tree inside the fence, in O(log n)? Fix corner 0 of the ccw hull; binary search the wedge (h[0], h[i], h[i+1]) containing the point with orient, then check one orient against side i → i + 1.

Hint

The point must satisfy orient(h[0], h[1], p) >= 0 and orient(h[0], h[m−1], p) <= 0; inside the wedge, it is inside if orient(h[i], h[i+1], p) >= 0.

3. Keep the trees on the sides too. Pop only on cross < 0, but then all-collinear inputs need care: the upper walk revisits the same points.

Hint

If every point is collinear, return the sorted points once. Otherwise < 0 works as in the buggy version.

4. The minimum width of the farm. The smallest distance between two parallel lines enclosing all trees: for each hull side, the farthest corner from it (the same calipers pointer) gives a width cross / |side|; take the minimum.

Hint

Compare widths as fractions cross² / |side|² to stay exact, or use long double only at the end.

Quick quiz

// trees: (0,0) (2,1) (4,0) (3,3) (1,2) (2,4) (0,4)
// how many corners has the convex hull?

A) 5 · B) 4 · C) 6 · D) 7

Answer

A. The hull is (0,0) (4,0) (3,3) (2,4) (0,4). (3,3) is a corner: the line from (4,0) to (2,4) passes x = 2.5 at y = 3. (2,1) and (1,2) are inside. (Checked with the program above.)

Interview questions

  1. What is a convex hull? The smallest convex polygon containing all the points; the shape of a rubber band around them.
  2. How does Andrew's monotone chain work? Sort by (x, y), build the lower and upper hulls with a stack, popping while the last two points and the new one are not a left turn.
  3. What is its complexity? O(n log n) for the sort plus O(n) for the walks.
  4. How do you exclude collinear points? Pop on cross ≤ 0; to keep them, pop on < 0 and handle the all-collinear case.
  5. Graham scan vs monotone chain? Graham sorts by angle around the lowest point; monotone chain sorts by x and avoids angle comparisons.
  6. How do you find the farthest pair? Both ends are hull corners; rotating calipers find it in O(h) after the hull.
  7. Why squared distances? They stay integers, so comparisons are exact.

Glossary

Term Meaning Example
Convex hull The tightest convex fence around points the square farm
Hull corner (vertex) A point where the fence turns (4,0)
Collinear point A point on a straight side, not a corner (2,0)
Monotone chain (Andrew) Sort by x, lower and upper hull with a stack O(n log n)
Graham scan Hull by sorting around one point by angle same complexity
Lower / upper hull The bottom / top part of the fence left→right / right→left
Stack pop Removing the last corner when a turn is wrong k--
cross <= 0 Not a left turn (right or straight) pop
Counterclockwise (CCW) The order of left turns the output order
unique Removes equal neighbours after sorting duplicate trees
Squared distance dx² + dy², an exact integer 52
Farthest pair (diameter) Two points with the largest distance (0,0)–(6,4)
Antipodal pair Two hull corners on parallel supporting lines calipers' pairs
Rotating calipers Two pointers going round the hull O(h)
Stress test Fast vs brute force on random inputs all 500 tests passed
Shoelace formula Polygon area from corners (next episode) —

Summary

  • Shortest fence = convex hull. Monotone chain: sort + unique, lower hull left→right, upper hull right→left, pop while cross <= 0, resize(k − 1).
  • <= 0 excludes points in the middle of sides; handle 1 point and all-collinear inputs.
  • Farthest pair: hull + rotating calipers, O(h); squared distances in long long.

Solutions in C++, Java and Python

Problem H1 · Fence the Farm

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    vector<P> h = convexHull(p);
    cout << h.size() << "\n";
    for (auto& v : h) cout << v.x << " " << v.y << "\n";   // counterclockwise
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static long cross(long[] o, long[] a, long[] b) {   // cross(a - o, b - a)
        return (a[0] - o[0]) * (b[1] - a[1]) - (a[1] - o[1]) * (b[0] - a[0]);
    }
    static List<long[]> convexHull(long[][] pts) {       // Andrew's monotone chain, counterclockwise
        long[][] p = pts.clone();
        Arrays.sort(p, (u, v) -> u[0] != v[0] ? Long.compare(u[0], v[0]) : Long.compare(u[1], v[1]));
        List<long[]> q = new ArrayList<>();
        for (long[] v : p) if (q.isEmpty() || q.get(q.size() - 1)[0] != v[0] || q.get(q.size() - 1)[1] != v[1]) q.add(v);
        int n = q.size();
        if (n < 3) return q;
        long[][] h = new long[2 * n][];
        int k = 0;
        for (int i = 0; i < n; i++) {                    // lower hull
            while (k >= 2 && cross(h[k - 2], h[k - 1], q.get(i)) <= 0) k--;
            h[k++] = q.get(i);
        }
        for (int i = n - 2, t = k + 1; i >= 0; i--) {    // upper hull
            while (k >= t && cross(h[k - 2], h[k - 1], q.get(i)) <= 0) k--;
            h[k++] = q.get(i);
        }
        return new ArrayList<>(Arrays.asList(h).subList(0, k - 1));
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        long[][] p = new long[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            p[i][0] = Long.parseLong(st.nextToken()); p[i][1] = Long.parseLong(st.nextToken());
        }
        List<long[]> h = convexHull(p);
        StringBuilder out = new StringBuilder().append(h.size()).append('\n');
        for (long[] v : h) out.append(v[0]).append(' ').append(v[1]).append('\n');
        System.out.print(out);
    }
}
4
0 0
4 0
4 4
0 4

Python

import sys

def cross(o, a, b):                      # cross(a - o, b - a)
    return (a[0] - o[0]) * (b[1] - a[1]) - (a[1] - o[1]) * (b[0] - a[0])

def convex_hull(points):                 # Andrew's monotone chain, counterclockwise
    p = sorted(set(points))
    if len(p) < 3:
        return p
    lower, upper = [], []
    for v in p:                          # lower hull, left to right
        while len(lower) >= 2 and cross(lower[-2], lower[-1], v) <= 0:
            lower.pop()
        lower.append(v)
    for v in reversed(p):                # upper hull, right to left
        while len(upper) >= 2 and cross(upper[-2], upper[-1], v) <= 0:
            upper.pop()
        upper.append(v)
    return lower[:-1] + upper[:-1]

data = list(map(int, sys.stdin.read().split()))
n = data[0]
pts = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
h = convex_hull(pts)
print(len(h))
for x, y in h:
    print(x, y)
4
0 0
4 0
4 4
0 4

Problem H2 · The Longest Pole

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }

ll dist2(P a, P b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }

vector<P> convexHull(vector<P> p) {                // Andrew's monotone chain, counterclockwise
    sort(p.begin(), p.end());                       // left to right
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), k = 0;
    if (n < 3) return p;
    vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {                   // lower hull, left to right
        while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;   // not a left turn: pop
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {   // upper hull, right to left
        while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                // the first corner was added twice
    return h;
}

ll farthest(const vector<P>& h) {                    // rotating calipers on a ccw hull
    int m = h.size();
    if (m == 1) return 0;
    if (m == 2) return dist2(h[0], h[1]);
    ll best = 0;
    for (int i = 0, j = 1; i < m; i++) {
        int ni = (i + 1) % m;
        while (cross(h[ni] - h[i], h[(j + 1) % m] - h[j]) > 0) j = (j + 1) % m;   // j: farthest from side i
        best = max({best, dist2(h[i], h[j]), dist2(h[ni], h[j])});
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    cout << farthest(convexHull(p)) << "\n";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static long cross(long[] o, long[] a, long[] b) {   // cross(a - o, b - a)
        return (a[0] - o[0]) * (b[1] - a[1]) - (a[1] - o[1]) * (b[0] - a[0]);
    }
    static List<long[]> convexHull(long[][] pts) {       // Andrew's monotone chain, counterclockwise
        long[][] p = pts.clone();
        Arrays.sort(p, (u, v) -> u[0] != v[0] ? Long.compare(u[0], v[0]) : Long.compare(u[1], v[1]));
        List<long[]> q = new ArrayList<>();
        for (long[] v : p) if (q.isEmpty() || q.get(q.size() - 1)[0] != v[0] || q.get(q.size() - 1)[1] != v[1]) q.add(v);
        int n = q.size();
        if (n < 3) return q;
        long[][] h = new long[2 * n][];
        int k = 0;
        for (int i = 0; i < n; i++) {                    // lower hull
            while (k >= 2 && cross(h[k - 2], h[k - 1], q.get(i)) <= 0) k--;
            h[k++] = q.get(i);
        }
        for (int i = n - 2, t = k + 1; i >= 0; i--) {    // upper hull
            while (k >= t && cross(h[k - 2], h[k - 1], q.get(i)) <= 0) k--;
            h[k++] = q.get(i);
        }
        return new ArrayList<>(Arrays.asList(h).subList(0, k - 1));
    }
    static long dist2(long[] a, long[] b) { long dx = a[0] - b[0], dy = a[1] - b[1]; return dx * dx + dy * dy; }
    static long farthest(List<long[]> h) {               // rotating calipers on a ccw hull
        int m = h.size();
        if (m == 1) return 0;
        if (m == 2) return dist2(h.get(0), h.get(1));
        long best = 0;
        for (int i = 0, j = 1; i < m; i++) {
            int ni = (i + 1) % m;
            while (true) {                               // move j while the next corner is farther from side i
                long[] a = h.get(i), b = h.get(ni), c = h.get(j), d = h.get((j + 1) % m);
                long cr = (b[0] - a[0]) * (d[1] - c[1]) - (b[1] - a[1]) * (d[0] - c[0]);
                if (cr > 0) j = (j + 1) % m; else break;
            }
            best = Math.max(best, Math.max(dist2(h.get(i), h.get(j)), dist2(h.get(ni), h.get(j))));
        }
        return best;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        long[][] p = new long[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            p[i][0] = Long.parseLong(st.nextToken()); p[i][1] = Long.parseLong(st.nextToken());
        }
        System.out.println(farthest(convexHull(p)));
    }
}
52

Python

import sys

def cross(o, a, b):                      # cross(a - o, b - a)
    return (a[0] - o[0]) * (b[1] - a[1]) - (a[1] - o[1]) * (b[0] - a[0])

def convex_hull(points):                 # Andrew's monotone chain, counterclockwise
    p = sorted(set(points))
    if len(p) < 3:
        return p
    lower, upper = [], []
    for v in p:                          # lower hull, left to right
        while len(lower) >= 2 and cross(lower[-2], lower[-1], v) <= 0:
            lower.pop()
        lower.append(v)
    for v in reversed(p):                # upper hull, right to left
        while len(upper) >= 2 and cross(upper[-2], upper[-1], v) <= 0:
            upper.pop()
        upper.append(v)
    return lower[:-1] + upper[:-1]

def dist2(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def farthest(h):                         # rotating calipers on a ccw hull
    m = len(h)
    if m == 1:
        return 0
    if m == 2:
        return dist2(h[0], h[1])
    best, j = 0, 1
    for i in range(m):
        ni = (i + 1) % m
        while True:                      # move j while the next corner is farther from side i
            a, b, c, d = h[i], h[ni], h[j], h[(j + 1) % m]
            if (b[0] - a[0]) * (d[1] - c[1]) - (b[1] - a[1]) * (d[0] - c[0]) > 0:
                j = (j + 1) % m
            else:
                break
        best = max(best, dist2(h[i], h[j]), dist2(h[ni], h[j]))
    return best

data = list(map(int, sys.stdin.read().split()))
n = data[0]
pts = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
print(farthest(convex_hull(pts)))
52