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
- Sort the points by x, then by y; remove duplicates.
- 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. - Upper hull, right to left, the same way (stop popping at the lower hull's size
t). - 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
- What is a convex hull? The smallest convex polygon containing all the points; the shape of a rubber band around them.
- 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.
- What is its complexity? O(n log n) for the sort plus O(n) for the walks.
- How do you exclude collinear points? Pop on
cross ≤ 0; to keep them, pop on< 0and handle the all-collinear case. - Graham scan vs monotone chain? Graham sorts by angle around the lowest point; monotone chain sorts by x and avoids angle comparisons.
- How do you find the farthest pair? Both ends are hull corners; rotating calipers find it in O(h) after the hull.
- 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). <= 0excludes 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