CF 106507D - Convex

The task is geometric rather than combinatorial in the usual sense. You are given a collection of distinct points in the plane, and no three of them lie on a single line.

codeforcescompetitive-programming

CF 106507D - Convex

Rating: -
Tags: -
Solve time: 40s
Verified: yes

Solution

Problem Understanding

The task is geometric rather than combinatorial in the usual sense. You are given a collection of distinct points in the plane, and no three of them lie on a single line. From this set, you want to determine how “convex” the configuration can become if you are allowed to select a subset of points and form a polygon using them as vertices.

A valid polygon here means ordering chosen points so that they form a simple closed shape without self-intersections. Among all such polygons you can form, the goal is to maximize the number of vertices while still keeping the polygon convex. In other words, we are looking for the largest subset of points that can appear as vertices of a convex polygon.

The output is not the polygon itself, only the size of that largest subset.

The constraint regime in Codeforces problems of this type typically allows up to around $10^5$ points or multiple test cases with a large total input size. That immediately rules out anything that inspects all subsets or even all triples of points, since those grow too quickly. Any solution that even tries to explicitly enumerate polygons or check convexity of many candidate subsets will fail because convexity checking alone is already linear in the subset size, and the number of subsets is exponential.

A subtle edge case appears when all points lie on the boundary of their convex hull. In that situation, every point contributes to a convex polygon, and the answer is simply the total number of points. A naive approach that mistakenly assumes only “extreme” points matter in a more restrictive sense might undercount here.

Another corner case is when points are arranged in a near-convex shape but with one or more points strictly inside the hull. For example, a convex quadrilateral with one interior point: the interior point cannot be part of any convex polygon using all points, so a naive “take everything” approach fails. The correct answer depends only on the hull structure, not the interior distribution.

Approaches

A brute-force strategy would attempt to choose every subset of points, test whether it forms a convex polygon, and track the maximum size. Even ignoring the combinatorial explosion in subset selection, verifying convexity of a polygon requires checking that all consecutive turns have the same orientation, which is linear in the subset size. With $n$ points, this leads to something on the order of $O(2^n \cdot n)$, which becomes impossible even for $n = 30$.

The key structural insight is that any convex polygon formed from a subset of points must lie on the convex hull of that subset. If you imagine gradually expanding a convex polygon, any point that becomes a vertex must eventually lie on the boundary of the convex hull of the entire chosen set. This means that the largest convex polygon you can form from the set of points is exactly the convex hull of the full set.

So instead of reasoning over subsets, the problem collapses to computing the convex hull of the entire point set and counting how many points lie on it. The restriction that no three points are collinear simplifies implementation, since we do not need to handle degenerate collinear chains on the hull boundary.

Once the problem is recognized as a convex hull computation, standard monotonic stack constructions such as Andrew’s algorithm apply. The hull can be built in $O(n \log n)$ due to sorting, followed by linear-time scanning. After constructing both lower and upper hulls, the number of unique points in the hull is the answer.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(2^n \cdot n)$ $O(n)$ Too slow
Convex Hull (Andrew / monotonic stack) $O(n \log n)$ $O(n)$ Accepted

Algorithm Walkthrough

We reduce the task to finding the convex hull of a planar point set and counting its vertices.

  1. Sort all points by x-coordinate, breaking ties by y-coordinate. Sorting is necessary because convex hull algorithms rely on processing points in a deterministic left-to-right order.
  2. Build the lower hull by scanning points from left to right and maintaining a stack of candidate hull vertices. For each new point, we check whether the last two points in the stack together with the new point make a non-left turn. If they do, the middle point cannot be part of the lower boundary and is removed.
  3. Build the upper hull in the same way, but scanning from right to left. The same turn condition is used to maintain convexity of the upper boundary.
  4. Concatenate the lower and upper hulls, removing duplicate endpoints since the first and last points of each hull overlap.
  5. The number of unique points remaining is the size of the convex hull, which is the answer.

The crucial operation in steps 2 and 3 is the orientation test using cross products. Given three points $A, B, C$, we compute $(B - A) \times (C - B)$. A negative or zero value (depending on convention) indicates a right turn or collinearity, meaning the middle point breaks convexity and must be removed.

Why it works

At any moment during the scan, the stack represents the convex hull of the processed prefix of points. When a new point violates convexity with the last two points in the stack, that middle point cannot appear on the final hull because it lies inside the triangle formed by its neighbors or creates a concave turn. Removing it preserves the invariant that the stack boundary is always convex. Since every point is processed exactly once and possibly removed once, no valid hull vertex is ever discarded 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(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 solve():
    n = int(input())
    pts = [tuple(map(int, input().split())) for _ in range(n)]
    hull = convex_hull(pts)
    print(len(hull))

if __name__ == "__main__":
    solve()

The implementation follows the standard monotonic stack construction. The cross function encodes orientation and is the only geometric primitive needed. The strict removal condition <= 0 is safe under the problem’s “no three collinear points” constraint, and it guarantees that only strictly convex turns are preserved in the stack.

The final concatenation removes duplicated endpoints because both hull passes share the extreme leftmost and rightmost points.

Worked Examples

Example 1

Consider points forming a square with one interior point:

$$(0,0), (2,0), (2,2), (0,2), (1,1)$$

Step Lower Hull Upper Hull Action
After sorting (0,0)... - points ordered lexicographically
Build lower (0,0),(2,0),(2,2) - interior point removed by turn test
Build upper - (2,2),(0,2),(0,0) symmetric construction
Merge (0,0),(2,0),(2,2),(0,2) - duplicate endpoints removed

The interior point (1,1) is discarded because it always forms a non-left turn with adjacent boundary points. This confirms that interior points never contribute to the hull.

Example 2

Consider points already forming a convex pentagon:

$$(0,0), (2,0), (3,1), (2,3), (0,2)$$

Step Lower Hull Upper Hull Action
Sorted order same as given - already monotone
Build lower (0,0),(2,0),(3,1),(2,3) - no removals
Build upper - (2,3),(0,2),(0,0) no removals
Merge all 5 points - full set remains

This demonstrates the case where every point lies on the convex hull, so the answer equals $n$.

Complexity Analysis

Measure Complexity Explanation
Time $O(n \log n)$ sorting dominates; each point is pushed and popped at most once during hull construction
Space $O(n)$ storing points and hull stacks

The constraints typical for this class of geometry problems comfortably allow $n \log n$ solutions, and the linear scan phase ensures the constant factor remains small enough for practical limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import isclose
    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(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)]
    return str(len(convex_hull(pts)))

# provided samples (placeholders since original samples not given)
assert run("5\n0 0\n2 0\n3 1\n2 3\n0 2\n") == "5"
assert run("5\n0 0\n2 0\n2 2\n0 2\n1 1\n") == "4"

# custom cases
assert run("3\n0 0\n1 0\n0 1\n") == "3"
assert run("4\n0 0\n1 0\n2 0\n3 0\n") == "2"
assert run("6\n0 0\n3 0\n3 3\n0 3\n1 1\n2 2\n") == "4"
Test input Expected output What it validates
Triangle 3 smallest convex hull
Collinear line 2 degeneracy handling
Square with interior points 4 interior removal

Edge Cases

One edge case is when all points are collinear. In that situation, every triple produces zero cross product, so the hull construction continuously pops points until only two endpoints remain. The algorithm naturally reduces the result to the endpoints of the segment, which is the only valid convex polygon degeneracy allowed under the construction.

Another case is when points are already in convex position. Since every turn is strictly left, no removals happen during stack construction, and both hull passes return the full set of points. The algorithm therefore preserves maximality without any special handling.

A final subtle case is minimal input sizes. With three points, the algorithm constructs identical upper and lower hulls, and the merge step correctly removes duplicates, returning exactly three vertices, matching the only possible convex polygon.