⚙️AlgorithmIntermediate

Convex Hull

Key Points

•
The convex hull is the smallest convex polygon that contains all given points, like a rubber band snapped around nails on a board.
•
Graham scan sorts points by polar angle around a pivot and uses a stack to remove right turns, running in O(n $lo g$ n) time.
•
Andrew’s monotone chain sorts by x then y and builds lower and upper hulls by discarding non-left turns, also O(n $lo g$ n).
•
Jarvis march (gift wrapping) walks around the hull by repeatedly choosing the next extreme point, taking O(nh) where h is hull size.
•
Orientation tests via cross products determine left vs right turns robustly with integer coordinates.
•
Handle duplicates and collinear points consistently to avoid degenerate or duplicated vertices in the hull.
•
For many downstream tasks (diameter, width, Minkowski sum), you first compute the convex hull and then apply rotating calipers in O(h).
•
Numerical stability is easiest with integer coordinates using 64-bit cross products; floating-point requires epsilons and careful comparisons.

Prerequisites

→Vector arithmetic in 2D — Convex hull algorithms rely on vector subtraction and cross products to test orientations.
→Sorting and comparators — Both Graham scan and Andrew’s algorithm require custom sorts with tiebreakers.
→Big-O notation — Understanding O(n \log n) vs O(nh) helps choose the right algorithm.
→Modular indexing and cyclic order — Hull traversal and rotating calipers use wrap-around indexing.
→Integer overflow and numeric stability — Orientation and distance calculations can overflow or be numerically unstable if mishandled.

Detailed Explanation

Tap terms for definitions

01Overview

The convex hull of a set of points in the plane is the smallest convex polygon that encloses all the points. Imagine stretching a rubber band around the outermost points; once released, the band forms the convex hull. Computing this hull is a foundational problem in computational geometry and a building block for many other algorithms such as closest pair approximations, farthest pair (diameter), rotating calipers applications, collision detection, and shape analysis. Several classic algorithms exist. Graham scan picks a pivot (e.g., the lowest-leftmost point), sorts remaining points by polar angle around this pivot, and then scans through them, maintaining a stack that represents the current hull and popping points that create right turns. Andrew’s monotone chain is a simpler and often faster-in-practice O(n log n) algorithm that sorts points lexicographically and constructs the lower and upper parts of the hull with a similar left-turn rule. Jarvis march (gift wrapping) simulates wrapping paper around the set, choosing the next point by angle each step; its time is O(nh), which can be preferable when the hull has few points. Correctness hinges on the orientation (left/right turn) test, typically implemented using the 2D cross product. Practical implementations must also handle duplicates and collinearity carefully to avoid repeated vertices or missing edge points. Once the convex hull is computed, many geometric queries can be answered efficiently on the hull instead of the entire set.

02Intuition & Analogies

Picture you have many nails hammered into a board. If you take a rubber band, stretch it around all nails, and let go, it will naturally snap to surround only the "outermost" nails, making a tight loop. That loop is your convex hull: every point inside is trapped, and the loop has no inward dents. If there were dents, you could straighten them to make a tighter band, so the convex hull must be dent-free and outwardly bulging everywhere. Now consider walking around the outer perimeter of a crowd. If you always choose your next step as the most leftward direction that still goes around everyone, you will eventually circle the crowd. This is Jarvis march: you keep turning left as little as needed to continue wrapping. Alternatively, suppose you sort people from left to right, then trace a path along the bottom edge, always eliminating those that make you turn right (a dent), and later do the same for the top edge. That is Andrew’s monotone chain: left-to-right order plus a "no-dents" rule. Graham scan’s intuition is similar but starts from a special anchor, the lowest-leftmost person, and sweeps in order of angle around that anchor. As you move, if adding someone makes you bend right (forming a dent), you step back to the last bend that kept your path outward. In all cases, the heart of the method is the left-vs-right decision, which can be made by the cross product sign: positive means a left turn (good for a counterclockwise hull), negative means a right turn (bad, must pop), and zero means collinear (handle depending on whether you want to include boundary collinear points).

03Formal Definition

Given a finite set of points S = {

p_{1}

p_{2}

, ...,

p_{n}

}

\subset

R^{2}

, the convex hull, denoted

conv

(S), is the smallest convex set containing S. Equivalently, it is the intersection of all convex sets that contain S. Another equivalent definition is the set of all convex combinations of points in S: all points of the form

\sum_{i = 1}^{n}

λ_{i}

p_{i}

where

λ_{i}

\geq

0 and

\sum_{i = 1}^{n}

λ_{i}

= 1. In 2D, if S is not collinear,

conv

(S) is a convex polygon whose vertices are a subset of S, ordered counterclockwise or clockwise along its boundary. The orientation predicate for three points a, b, c is given by the sign of the scalar cross product (b - a)

\times

(c - a) = (

b_{x}

a_{x}

)(

c_{y}

a_{y}

) - (

b_{y}

a_{y}

)(

c_{x}

a_{x}

). A positive value indicates that c lies to the left of the directed line a

\to

b (a counterclockwise turn), negative indicates a right (clockwise) turn, and zero indicates collinearity. Algorithmically, Graham scan sorts points by polar angle around an anchor and uses a stack to maintain a convex chain, discarding points that cause right turns. Andrew’s monotone chain sorts lexicographically and builds two convex chains (lower and upper) similarly. Jarvis march iteratively selects the next hull vertex by choosing the point that forms the most counterclockwise turn from the current edge.

04When to Use

Use convex hull algorithms whenever you need the outer boundary of a point set for shape analysis, simplification, or as a preprocessing step for more advanced geometric tasks.

Preprocessing for farthest pair (diameter): Compute the hull, then apply rotating calipers in O(h) to find the maximum distance; this is faster than checking all O(n^2) pairs when h \ll n.
Collision detection and separating axis theorem: Operating on the hull reduces complexity and improves robustness.
Computing the width, minimum bounding rectangle, or rotating calipers-derived measures: These often run in O(h) after the hull is known.
Map generalization and boundary extraction in GIS: The hull approximates the border of a spatial cluster.
Outlier detection and shape descriptors in computer vision: The hull provides a compact representation of object extent. Algorithm choice: If you expect many points with a relatively small hull (h small), Jarvis march (O(nh)) can be effective. For general-purpose use, Andrew’s monotone chain is straightforward, robust with integer inputs, and O(n \log n) due to sorting. Graham scan is also O(n \log n) and instructive but requires careful polar-angle sorting and tie handling. In streaming or online settings, incremental hull maintenance or dynamic hull data structures may be preferable.

⚠️Common Mistakes

Mishandling collinear points: Decide whether you want all boundary collinear points on the hull or only the extreme endpoints. In Andrew’s algorithm, using "<= 0" vs "< 0" in the orientation check changes this; document your choice consistently.
Forgetting to remove duplicates: Duplicate points can cause repeated vertices or zero-length edges. Deduplicate after sorting to simplify logic.
Integer overflow in cross products: With 32-bit ints, cross products can overflow. Use 64-bit integers (long long) for coordinates up to about 1e9, or use built-in big integers if necessary.
Floating-point robustness: When using doubles, small numerical errors can flip orientation signs. Introduce an epsilon threshold and stable comparisons, or prefer integer arithmetic if possible.
Wrong angle comparator in Graham scan: When sorting by polar angle, handle collinear ties by keeping the farthest point last (and optionally removing interior collinear points beforehand), otherwise the scan may backtrack incorrectly.
Not closing the hull: Many downstream formulas (area via shoelace, perimeter) assume cyclic order; ensure the first point is appended at the end or handle indices modulo h.
Assuming O(n) hull building: Sorting dominates cost for comparison-based methods; total time is O(n \log n). Don’t claim O(n) unless input is pre-sorted or specialized bucketing is used.

Key Formulas

Convex Hull as Intersection

conv (S) = ⋂ {C \subseteq R^{2} ∣ C convex and S \subseteq C}

Explanation: The convex hull is the intersection of all convex sets that contain the point set S. This states it is the smallest convex container of S.

Convex Combinations

conv (S) = {i = 1 \sum n λ_{i} p_{i} p_{i} \in S, λ_{i} \geq 0, i = 1 \sum n λ_{i} = 1}

Explanation: Every point in the convex hull can be expressed as a weighted average of input points with nonnegative weights summing to one. This is a constructive definition.

2D Cross Product / Orientation

cross (ab, a c) = (b_{x} - a_{x}) (c_{y} - a_{y}) - (b_{y} - a_{y}) (c_{x} - a_{x})

Explanation: The sign of this value tells whether the triple (a,b,c) makes a left turn (>0), is collinear (=0), or makes a right turn (<0). It is the core predicate for hull algorithms.

Graham/Andrew Complexity

T (n) = O (n lo g n)

Explanation: Both Graham scan and Andrew’s monotone chain take O(n log n) time because they sort the points and then do a linear pass to build the hull. Sorting dominates the cost.

Jarvis March Complexity

T (n, h) = O (nh)

Explanation: Gift wrapping selects one hull vertex per pass while scanning all n points to find the next. If the hull has h vertices, the total time is proportional to n times h.

Shoelace Area

A = \frac{1}{2} i = 1 \sum h x_{i} y_{i + 1} - x_{i + 1} y_{i}, x_{h + 1} = x_{1}, y_{h + 1} = y_{1}

Explanation: Given the convex hull vertices in order, this computes the polygon’s area. The last term wraps around to the first to close the polygon.

Squared Distance

d^{2} (a, b) = (a_{x} - b_{x})^{2} + (a_{y} - b_{y})^{2}

Explanation: Using squared distance avoids expensive square roots and preserves order comparisons when searching for farthest or nearest pairs.

Sorting Lower Bound (Informal)

n lo g n \geq c \cdot n for n \geq 2

Explanation: Comparison-based sorting needs at least proportional to n log n comparisons in the worst case, implying general convex hull algorithms that rely on sorting cannot do better asymptotically.

Hull Size Bound

h \leq n

Explanation: The number of hull vertices cannot exceed the total number of input points. This parameter h influences output-sensitive algorithms like Jarvis march.

Complexity Analysis

Let n be the number of input points and h the number of vertices on the convex hull. For Graham scan and Andrew’s monotone chain, the dominant step is sorting: lexicographic sort or angular sort costs O(n log n). The subsequent linear passes maintain a stack or dynamic list, each point being pushed and popped at most once, giving O(n) additional time. Thus, the total time complexity is O(n log n), and the algorithms are comparison-based. The space complexity is O(n): you store the sorted points and the hull stack or vector, which in the worst case may hold up to n points; auxiliary variables contribute O(1). Jarvis march (gift wrapping) is output-sensitive: in each of h steps (one per hull vertex), it scans all n points to choose the most counterclockwise next point by comparing orientations, for a time of O(nh). Its space usage is O(1) beyond the output hull, since it keeps only the current index and best candidate. For downstream computations on the hull, rotating calipers methods typically take O(h) time, since they sweep around the convex polygon once while maintaining antipodal pairs or supporting lines. Examples include computing the diameter (farthest pair), minimum width, and certain bounding boxes. Space is O(1) beyond the hull. In practice, careful handling of duplicates and collinearities avoids extra pops or degeneracies but does not change asymptotic costs. When using integer coordinates up to about 10^9, cross products require 64-bit signed integers to avoid overflow: the cross value may be as large as approximately 2·(10^9)^2 ≈ 2·10^18, which fits within signed 64-bit range but leaves little headroom; be cautious when summing many such values (e.g., area), perhaps using built-in 128-bit intermediates where available.

Code Examples

Andrew's Monotone Chain Convex Hull (integer-safe, keeps boundary collinear points)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Point {
5     long long x, y;
6     bool operator<(const Point& other) const {
7         if (x != other.x) return x < other.x;
8         return y < other.y;
9     }
10     bool operator==(const Point& other) const {
11         return x == other.x && y == other.y;
12     }
13 };
14 
15 // Cross product of (b - a) and (c - a)
16 static inline long long cross(const Point& a, const Point& b, const Point& c) {
17     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
18 }
19 
20 // Monotone chain: returns hull in CCW order without duplicate last point
21 // This version keeps boundary collinear points on edges by using cross <= 0 when popping for CCW hull.
22 vector<Point> convex_hull(vector<Point> pts) {
23     int n = (int)pts.size();
24     if (n <= 1) return pts;
25 
26     sort(pts.begin(), pts.end());
27     pts.erase(unique(pts.begin(), pts.end()), pts.end());
28     n = (int)pts.size();
29     if (n <= 1) return pts;
30 
31     vector<Point> lower, upper;
32 
33     // Build lower hull
34     for (const auto& p : pts) {
35         while (lower.size() >= 2 && cross(lower[lower.size()-2], lower.back(), p) < 0) {
36             // Use < 0 to keep collinear points; use <= 0 to remove them (only extremes kept)
37             lower.pop_back();
38         }
39         lower.push_back(p);
40     }
41 
42     // Build upper hull
43     for (int i = n - 1; i >= 0; --i) {
44         const auto& p = pts[i];
45         while (upper.size() >= 2 && cross(upper[upper.size()-2], upper.back(), p) < 0) {
46             upper.pop_back();
47         }
48         upper.push_back(p);
49     }
50 
51     // Concatenate lower and upper to get full hull; omit last of each to avoid duplicates
52     lower.pop_back();
53     upper.pop_back();
54     vector<Point> hull = lower;
55     hull.insert(hull.end(), upper.begin(), upper.end());
56 
57     return hull; // CCW order, may include collinear boundary points
58 }
59 
60 int main() {
61     ios::sync_with_stdio(false);
62     cin.tie(nullptr);
63 
64     int n; cin >> n;
65     vector<Point> pts(n);
66     for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
67 
68     auto hull = convex_hull(pts);
69 
70     cout << hull.size() << "\n";
71     for (auto& p : hull) cout << p.x << ' ' << p.y << '\n';
72     return 0;
73 }
74

This implementation sorts points lexicographically, removes duplicates, and constructs the lower and upper chains. The orientation check uses the integer cross product. The pop condition uses < 0 to keep collinear points on the hull edges; switch to <= 0 if you want to exclude intermediate collinear points and keep only extremes.

Time: O(n log n)Space: O(n)

Graham Scan Convex Hull (polar-angle sort around pivot, excluding interior collinear points)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Point {
5     long long x, y;
6 };
7 
8 static inline long long cross(const Point& a, const Point& b, const Point& c) {
9     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
10 }
11 
12 static inline long long dist2(const Point& a, const Point& b) {
13     long long dx = a.x - b.x, dy = a.y - b.y;
14     return dx*dx + dy*dy;
15 }
16 
17 int main() {
18     ios::sync_with_stdio(false);
19     cin.tie(nullptr);
20 
21     int n; cin >> n;
22     vector<Point> pts(n);
23     for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
24 
25     // Handle small cases
26     if (n <= 1) {
27         cout << n << "\n";
28         if (n == 1) cout << pts[0].x << ' ' << pts[0].y << "\n";
29         return 0;
30     }
31 
32     // Find pivot: lowest y, then lowest x
33     int p0 = 0;
34     for (int i = 1; i < n; ++i) {
35         if (pts[i].y < pts[p0].y || (pts[i].y == pts[p0].y && pts[i].x < pts[p0].x)) p0 = i;
36     }
37     swap(pts[0], pts[p0]);
38     Point pivot = pts[0];
39 
40     // Sort by polar angle around pivot; if collinear with pivot, farthest last
41     sort(pts.begin() + 1, pts.end(), [&](const Point& a, const Point& b) {
42         long long cr = cross(pivot, a, b);
43         if (cr == 0) return dist2(pivot, a) < dist2(pivot, b); // closer first
44         return cr > 0; // a before b if left of pivot->b
45     });
46 
47     // Remove points collinear with pivot except the farthest (to avoid interior points)
48     vector<Point> unique_pts; unique_pts.reserve(n);
49     unique_pts.push_back(pivot);
50     for (int i = 1; i < n; ) {
51         int j = i;
52         // group by same direction (collinear w.r.t pivot)
53         while (j + 1 < n && cross(pivot, pts[j], pts[j+1]) == 0) ++j;
54         unique_pts.push_back(pts[j]); // keep farthest in this direction
55         i = j + 1;
56     }
57 
58     if ((int)unique_pts.size() == 1) {
59         cout << 1 << "\n" << unique_pts[0].x << ' ' << unique_pts[0].y << "\n";
60         return 0;
61     }
62 
63     vector<Point> st;
64     st.push_back(unique_pts[0]);
65     st.push_back(unique_pts[1]);
66     for (size_t i = 2; i < unique_pts.size(); ++i) {
67         while (st.size() >= 2 && cross(st[st.size()-2], st.back(), unique_pts[i]) <= 0) {
68             // <= 0 removes right turns and collinear points (keeping outer boundary only)
69             st.pop_back();
70         }
71         st.push_back(unique_pts[i]);
72     }
73 
74     cout << st.size() << "\n";
75     for (auto &p : st) cout << p.x << ' ' << p.y << "\n";
76     return 0;
77 }
78

This Graham scan selects a pivot, sorts by polar angle using the cross product, and removes interior collinear points. The stack pops when a non-left turn is detected (<= 0), ensuring a strictly convex CCW hull with only extreme vertices.

Time: O(n log n)Space: O(n)

Jarvis March (Gift Wrapping) with Integer Orientation

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Point { long long x, y; };
5 
6 static inline long long cross(const Point& a, const Point& b, const Point& c) {
7     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
8 }
9 
10 static inline long long dist2(const Point& a, const Point& b) {
11     long long dx = a.x - b.x, dy = a.y - b.y;
12     return dx*dx + dy*dy;
13 }
14 
15 int main(){
16     ios::sync_with_stdio(false);
17     cin.tie(nullptr);
18 
19     int n; cin >> n;
20     vector<Point> pts(n);
21     for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
22     if (n == 0) { cout << 0 << "\n"; return 0; }
23     if (n == 1) { cout << 1 << "\n" << pts[0].x << ' ' << pts[0].y << "\n"; return 0; }
24 
25     // Find leftmost (then lowest) point to start
26     int left = 0;
27     for (int i = 1; i < n; ++i) {
28         if (pts[i].x < pts[left].x || (pts[i].x == pts[left].x && pts[i].y < pts[left].y)) left = i;
29     }
30 
31     vector<Point> hull;
32     int p = left;
33     do {
34         hull.push_back(pts[p]);
35         int q = (p + 1) % n;
36         for (int r = 0; r < n; ++r) {
37             if (r == p) continue;
38             long long cr = cross(pts[p], pts[q], pts[r]);
39             if (cr < 0 || (cr == 0 && dist2(pts[p], pts[r]) > dist2(pts[p], pts[q]))) {
40                 // Choose more counterclockwise point, or farther if collinear
41                 q = r;
42             }
43         }
44         p = q;
45     } while (p != left);
46 
47     cout << hull.size() << "\n";
48     for (auto &pt : hull) cout << pt.x << ' ' << pt.y << "\n";
49     return 0;
50 }
51

Jarvis march starts at the leftmost point and repeatedly selects the next vertex as the most counterclockwise choice by scanning all points. Ties on collinearity are broken by taking the farthest point to avoid early termination along an edge.

Time: O(nh)Space: O(1) extra beyond output

Rotating Calipers: Diameter (Farthest Pair) from a Convex Hull

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Point { long long x, y; };
5 
6 static inline long long cross_ll(const Point& a, const Point& b, const Point& c) {
7     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
8 }
9 
10 static inline long long dist2(const Point& a, const Point& b) {
11     long long dx = a.x - b.x, dy = a.y - b.y;
12     return dx*dx + dy*dy;
13 }
14 
15 // Andrew's hull that excludes intermediate collinear points (keeps only extremes)
16 vector<Point> convex_hull(vector<Point> pts) {
17     sort(pts.begin(), pts.end(), [](const Point& A, const Point& B){
18         if (A.x != B.x) return A.x < B.x;
19         return A.y < B.y;
20     });
21     pts.erase(unique(pts.begin(), pts.end(), [](const Point& A, const Point& B){
22         return A.x == B.x && A.y == B.y;
23     }), pts.end());
24     if (pts.size() <= 1) return pts;
25 
26     vector<Point> H;
27     // lower
28     for (auto &p : pts) {
29         while (H.size() >= 2 && cross_ll(H[H.size()-2], H.back(), p) <= 0) H.pop_back();
30         H.push_back(p);
31     }
32     // upper
33     size_t t = H.size()+1;
34     for (int i = (int)pts.size()-2; i >= 0; --i) {
35         auto &p = pts[i];
36         while (H.size() >= t && cross_ll(H[H.size()-2], H.back(), p) <= 0) H.pop_back();
37         H.push_back(p);
38     }
39     H.pop_back();
40     return H; // CCW, no duplicate end
41 }
42 
43 // Rotating calipers to compute maximum squared distance on convex polygon H (CCW order)
44 long long diameter2(const vector<Point>& H) {
45     int h = (int)H.size();
46     if (h == 1) return 0;
47     if (h == 2) return dist2(H[0], H[1]);
48 
49     long long best = 0;
50     int j = 1;
51     for (int i = 0; i < h; ++i) {
52         int ni = (i + 1) % h;
53         // advance j while area (parallelogram) increases
54         while (true) {
55             int nj = (j + 1) % h;
56             long long cur = llabs(cross_ll(H[i], H[ni], H[j]));
57             long long nxt = llabs(cross_ll(H[i], H[ni], H[nj]));
58             if (nxt > cur) j = nj; else break;
59         }
60         best = max(best, dist2(H[i], H[j]));
61         best = max(best, dist2(H[ni], H[j]));
62     }
63     return best;
64 }
65 
66 int main(){
67     ios::sync_with_stdio(false);
68     cin.tie(nullptr);
69 
70     int n; cin >> n;
71     vector<Point> pts(n);
72     for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
73 
74     auto H = convex_hull(pts);
75     long long ans2 = diameter2(H);
76     cout << ans2 << "\n"; // squared diameter
77     return 0;
78 }
79

First compute the convex hull (excluding interior collinear points) and then apply rotating calipers to find the farthest pair in O(h). The calipers advance the antipodal index j to maximize the area of the parallelogram formed by each edge, which correlates with the farthest distances.

Time: O(n log n) to build hull, then O(h) for diameterSpace: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Point {
5	long long x, y;
6	bool operator<(const Point& other) const {
7	if (x != other.x) return x < other.x;
8	return y < other.y;
9	}
10	bool operator==(const Point& other) const {
11	return x == other.x && y == other.y;
12	}
13	};
14
15	// Cross product of (b - a) and (c - a)
16	static inline long long cross(const Point& a, const Point& b, const Point& c) {
17	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
18	}
19
20	// Monotone chain: returns hull in CCW order without duplicate last point
21	// This version keeps boundary collinear points on edges by using cross <= 0 when popping for CCW hull.
22	vector<Point> convex_hull(vector<Point> pts) {
23	int n = (int)pts.size();
24	if (n <= 1) return pts;
25
26	sort(pts.begin(), pts.end());
27	pts.erase(unique(pts.begin(), pts.end()), pts.end());
28	n = (int)pts.size();
29	if (n <= 1) return pts;
30
31	vector<Point> lower, upper;
32
33	// Build lower hull
34	for (const auto& p : pts) {
35	while (lower.size() >= 2 && cross(lower[lower.size()-2], lower.back(), p) < 0) {
36	// Use < 0 to keep collinear points; use <= 0 to remove them (only extremes kept)
37	lower.pop_back();
38	}
39	lower.push_back(p);
40	}
41
42	// Build upper hull
43	for (int i = n - 1; i >= 0; --i) {
44	const auto& p = pts[i];
45	while (upper.size() >= 2 && cross(upper[upper.size()-2], upper.back(), p) < 0) {
46	upper.pop_back();
47	}
48	upper.push_back(p);
49	}
50
51	// Concatenate lower and upper to get full hull; omit last of each to avoid duplicates
52	lower.pop_back();
53	upper.pop_back();
54	vector<Point> hull = lower;
55	hull.insert(hull.end(), upper.begin(), upper.end());
56
57	return hull; // CCW order, may include collinear boundary points
58	}
59
60	int main() {
61	ios::sync_with_stdio(false);
62	cin.tie(nullptr);
63
64	int n; cin >> n;
65	vector<Point> pts(n);
66	for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
67
68	auto hull = convex_hull(pts);
69
70	cout << hull.size() << "\n";
71	for (auto& p : hull) cout << p.x << ' ' << p.y << '\n';
72	return 0;
73	}
74

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Point { long long x, y; };
5
6	static inline long long cross(const Point& a, const Point& b, const Point& c) {
7	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
8	}
9
10	static inline long long dist2(const Point& a, const Point& b) {
11	long long dx = a.x - b.x, dy = a.y - b.y;
12	return dxdx + dydy;
13	}
14
15	int main(){
16	ios::sync_with_stdio(false);
17	cin.tie(nullptr);
18
19	int n; cin >> n;
20	vector<Point> pts(n);
21	for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
22	if (n == 0) { cout << 0 << "\n"; return 0; }
23	if (n == 1) { cout << 1 << "\n" << pts[0].x << ' ' << pts[0].y << "\n"; return 0; }
24
25	// Find leftmost (then lowest) point to start
26	int left = 0;
27	for (int i = 1; i < n; ++i) {
28	if (pts[i].x < pts[left].x \|\| (pts[i].x == pts[left].x && pts[i].y < pts[left].y)) left = i;
29	}
30
31	vector<Point> hull;
32	int p = left;
33	do {
34	hull.push_back(pts[p]);
35	int q = (p + 1) % n;
36	for (int r = 0; r < n; ++r) {
37	if (r == p) continue;
38	long long cr = cross(pts[p], pts[q], pts[r]);
39	if (cr < 0 \|\| (cr == 0 && dist2(pts[p], pts[r]) > dist2(pts[p], pts[q]))) {
40	// Choose more counterclockwise point, or farther if collinear
41	q = r;
42	}
43	}
44	p = q;
45	} while (p != left);
46
47	cout << hull.size() << "\n";
48	for (auto &pt : hull) cout << pt.x << ' ' << pt.y << "\n";
49	return 0;
50	}
51