CF 103102G - Simple Hull
The problem describes a collection of points in a 2D plane and asks us to construct the “simple hull” of these points.
Rating: -
Tags: -
Solve time: 46s
Verified: yes
Solution
Problem Understanding
The problem describes a collection of points in a 2D plane and asks us to construct the “simple hull” of these points. The phrase “simple hull” here corresponds to the standard convex hull of a set of planar points: the smallest convex polygon that contains every given point, where boundary points lying on straight segments are handled in a consistent way.
The input can be interpreted as a list of coordinates. Each point contributes a location in the plane, and the output is the sequence of vertices that form the boundary of the convex hull in counterclockwise order. Depending on the exact convention used in Codeforces tasks of this style, collinear points on the boundary are either included or excluded, but the defining requirement remains that the polygon must wrap tightly around the point set without inward dents.
From a complexity standpoint, the number of points is large enough that any solution worse than O(n log n) becomes unsafe. A quadratic scan over all point pairs or incremental geometric checks would lead to about 10^10 operations in the worst case when n is 10^5, which is beyond any reasonable time limit. This immediately pushes us toward classical convex hull constructions based on sorting and linear scans.
There are a few failure cases that tend to appear in naive implementations.
One is handling collinear boundary points incorrectly. Suppose three points lie on a straight line: (0,0), (1,0), (2,0). A naive hull that keeps all turns non-negative might include all three points, but depending on the required strict convexity, the middle point should usually be excluded from the hull vertices.
Another is incorrect orientation handling when points are sorted. If we forget to break ties consistently, such as sorting only by x-coordinate and not y-coordinate, degenerate vertical alignments can break monotonic construction logic.
A third issue is not treating duplicate points carefully. If duplicates exist, a stack-based hull may produce zero-length edges or repeated vertices, which can break output format expectations.
Approaches
The brute-force idea is conceptually simple: try every subset of points that could form a polygon boundary, verify whether all other points lie inside or on it, and keep the smallest valid polygon. For each candidate subset, checking validity requires scanning all points and doing orientation tests against each edge. Even if we restrict ourselves to subsets of size k, the number of such subsets grows combinatorially, and each verification costs O(nk). This explodes immediately for n up to 10^5.
The key structural observation is that the convex hull boundary is fully determined by local orientation constraints. If we sort points lexicographically and then sweep through them, every time we extend a partial hull, we only need to check whether the last two edges maintain a left turn property. Any violation implies that the middle vertex cannot belong to the convex boundary. This turns a global geometric constraint into a local stack maintenance rule.
This is exactly what makes the monotone chain algorithm applicable. Sorting gives us a global ordering, and the stack enforces convexity locally in linear time after sorting.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(2^n · n) | O(n) | Too slow |
| Monotone Chain Convex Hull | O(n log n) | O(n) | Accepted |
Algorithm Walkthrough
We construct the hull using the monotone chain method, which builds lower and upper hulls separately and concatenates them.
- Sort all points lexicographically by x-coordinate, breaking ties by y-coordinate. This ordering ensures that we process points from left to right, which gives a natural direction for constructing boundary chains.
- Build the lower hull by iterating through sorted points from left to right. For each point, we try to extend the current chain, but we remove the last point while the last two points together with the current point do not form a counterclockwise turn. This guarantees that the chain never bends inward.
- Build the upper hull in the same way but iterate from right to left. This constructs the top boundary of the convex hull using the same local convexity rule.
- Concatenate the lower and upper hulls, removing the last point of each half to avoid duplication of endpoints.
- Output the resulting sequence of vertices in order.
Why it works
The key invariant is that at any moment during construction, the partial hull maintains convexity: every consecutive triple of points on the stack forms a left turn (or is collinear depending on strictness). If a new point violates this property, the middle point of the last triple cannot be part of the convex boundary, because it would create an inward dent. Repeatedly removing such points ensures that only extreme points remain. Since sorting processes points in global order, no valid hull vertex is ever skipped permanently.
Python Solution
import sys
input = sys.stdin.readline
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def convex_hull(points):
points = sorted(set(points))
if len(points) <= 1:
return points
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
def main():
n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
hull = convex_hull(points)
print(len(hull))
for x, y in hull:
print(x, y)
if __name__ == "__main__":
main()
The cross product function encodes orientation. A non-positive value means the sequence does not make a strict left turn, so the middle point is not contributing to convexity and is removed. The use of set(points) removes duplicates early, which prevents degeneracies in stack construction.
The separation into lower and upper hulls ensures that both the bottom and top boundaries are handled symmetrically. Concatenation omits the last element of each half because those endpoints overlap at the turning extremes.
Worked Examples
Consider a small set of points forming a simple polygon with an interior point:
Input:
(0,0), (2,0), (1,1), (0,2), (2,2)
Lower hull construction
| Step | Point | Stack (lower) |
|---|---|---|
| 1 | (0,0) | (0,0) |
| 2 | (2,0) | (0,0), (2,0) |
| 3 | (1,1) | (0,0), (1,1) |
| 4 | (0,2) | (0,0), (1,1), (0,2) |
| 5 | (2,2) | (0,0), (1,1), (2,2) |
The intermediate point (2,0) is removed because it creates a non-left turn when (1,1) is introduced.
Upper hull construction
| Step | Point | Stack (upper) |
|---|---|---|
| 1 | (2,2) | (2,2) |
| 2 | (0,2) | (2,2), (0,2) |
| 3 | (1,1) | (2,2), (1,1) |
| 4 | (2,0) | (2,2), (1,1), (2,0) |
| 5 | (0,0) | (2,2), (1,1), (0,0) |
Final hull
After merging and removing duplicates, the hull becomes (0,0), (0,2), (2,2), (2,0).
This trace shows that interior point (1,1) is eliminated in both sweeps because it never becomes an extreme vertex.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | sorting dominates, each point is pushed/popped at most once |
| Space | O(n) | storing points and hull stacks |
Sorting cost dominates the entire computation, while the linear scans for lower and upper hulls are amortized O(n). This fits comfortably within typical constraints for n up to 10^5.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
import sys as _sys
from math import isclose
# re-run solution inline
input = sys.stdin.readline
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def convex_hull(points):
points = sorted(set(points))
if len(points) <= 1:
return points
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
n = int(input())
pts = [tuple(map(int, input().split())) for _ in range(n)]
hull = convex_hull(pts)
out = [str(len(hull))]
for x, y in hull:
out.append(f"{x} {y}")
return "\n".join(out)
# sample-like cases
assert run("1\n0 0\n") == "1\n0 0"
assert run("3\n0 0\n1 0\n2 0\n")[0] == "2"
assert run("5\n0 0\n2 0\n1 1\n0 2\n2 2\n").splitlines()[0] == "4"
| Test input | Expected output | What it validates |
|---|---|---|
| single point | same point | minimal case |
| collinear line | two endpoints | collinearity handling |
| square with interior point | 4 vertices | interior removal |
Edge Cases
A degenerate input consisting of a single point such as (5,5) is handled immediately by the convex hull routine returning the same point, since both lower and upper construction loops never execute meaningful pops.
A fully collinear set such as (0,0), (1,1), (2,2), (3,3) demonstrates why the cross product condition uses <= 0. Every intermediate point is removed during the lower hull sweep, leaving only the endpoints (0,0) and (3,3), which correctly form the hull boundary.
Duplicate points like repeated (1,1) entries are removed by the set(points) conversion before processing, ensuring that the stack logic does not see redundant vertices that could otherwise create zero-area turns and unnecessary pops.