Overview

Given \(N\) points, the problem asks us to select some points to form a strictly convex polygon with the maximum possible area, and output twice the value of that area.

Approach

To maximize the area, we need to select points that are as far outward as possible to enclose a large region. This is essentially equivalent to finding the “Convex Hull” that encompasses all the given points.

A naive approach would be to try all combinations (subsets) of points, form polygons, and compute their areas. However, this method has \(O(2^N)\) possible selections of points, which is far too slow to meet the time limit (resulting in TLE) given the large constraint of \(N \le 2 \times 10^5\). Therefore, an efficient algorithm for computing the convex hull is needed.

Additionally, due to the “strictly convex polygon” condition in the problem statement, we must be careful not to select points that lie on the edges of the convex polygon (points where the interior angle is \(180\) degrees).

Algorithm

We use the Monotone Chain algorithm to compute the convex hull.

1. Sorting the points: First, sort all points in ascending order of \(x\)-coordinate (breaking ties by ascending \(y\)-coordinate).
2. Constructing the lower hull: Iterate through the sorted points in order to build the lower half of the boundary (lower hull). When adding a new point \(C\), use the cross product to determine whether the last three points \(A, B, C\) form a “counterclockwise (left turn)”. If they form a clockwise turn or are collinear, remove the preceding point \(B\) until the condition is satisfied.
3. Constructing the upper hull: Now iterate through the points in reverse order (right to left) and apply the same procedure to build the upper half of the boundary (upper hull).
4. Computing the area: Combine the lower hull and upper hull to obtain the complete convex hull. Apply the “polygon area formula (Shoelace formula / Surveyor’s formula)” to the resulting set of vertices. When the vertices are ordered as \((x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)\), twice the area can be computed as the absolute value of \(\sum_{i=1}^k (x_i y_{i+1} - x_{i+1} y_i)\) (where \(x_{k+1}=x_1, y_{k+1}=y_1\)).

Complexity

• Time complexity: \(O(N \log N)\) Sorting the points takes \(O(N \log N)\). In the convex hull construction and area computation, each point is “added” to and “removed” from the list at most once, resulting in an amortized \(O(N)\) complexity. Overall, this runs very efficiently in \(O(N \log N)\).
• Space complexity: \(O(N)\) Memory proportional to the list of input coordinates and the list of vertices forming the convex hull is used.

Implementation Details

• Cross product check and the “strict” condition: For points \(A = (ax, ay)\), \(B = (bx, by)\), \(C = (cx, cy)\), the cross product of vectors \(AB\) and \(AC\) is computed as (bx - ax) * (cy - ay) - (by - ay) * (cx - ax). If this value is positive, the turn is counterclockwise; if \(0\), the points are collinear; if negative, the turn is clockwise. By using the condition <= (less than or equal to \(0\)) in the code to remove point \(B\), collinear points (points on the edge where the interior angle is \(180\) degrees) are automatically excluded, easily satisfying the “strictly convex polygon” condition.

• Avoiding errors through integer arithmetic: Since all coordinates are given as integers, there is no need to use division (floating-point numbers) in the cross product checks or the computation of twice the area. By performing all calculations using integer types, incorrect answers (WA) due to floating-point rounding errors can be completely avoided.

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    n = int(data[0])
    points = []
    idx = 1
    for _ in range(n):
        points.append((int(data[idx]), int(data[idx+1])))
        idx += 2
        
    points.sort()
    
    lower = []
    for p in points:
        while len(lower) >= 2:
            ax, ay = lower[-2]
            bx, by = lower[-1]
            cx, cy = p
            if (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) <= 0:
                lower.pop()
            else:
                break
        lower.append(p)
        
    upper = []
    for p in reversed(points):
        while len(upper) >= 2:
            ax, ay = upper[-2]
            bx, by = upper[-1]
            cx, cy = p
            if (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) <= 0:
                upper.pop()
            else:
                break
        upper.append(p)
        
    hull = lower[:-1] + upper[:-1]
    
    area_twice = 0
    k = len(hull)
    for i in range(k):
        x1, y1 = hull[i]
        x2, y2 = hull[(i + 1) % k]
        area_twice += x1 * y2 - x2 * y1
        
    print(abs(area_twice))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.