Overview

This problem asks us to select some points from the given \(N\) points to form a “strictly convex polygon” and find twice the maximum possible area of such a polygon.

In conclusion, this problem reduces to finding the Convex Hull of the entire given point set and computing its area.

Analysis

1. How to Maximize the Area?

When selecting points from a set of points on a plane to form a convex polygon, to maximize the area, we should choose points that are as “outer” as possible. The smallest convex polygon that encloses all given points is called the convex hull. Including any point that lies inside or on the boundary of the convex hull will never produce an area larger than the convex hull itself. Therefore, to maximize the area, we should select the points that form the vertices of the overall convex hull.

2. The “Strictly Convex Polygon” Condition

The problem states the condition that “all interior angles must be less than 180 degrees” (strictly convex polygon). This means that no points other than the vertices may exist on the edges of the convex polygon.

For example, if three points \(A, B, C\) are collinear in that order, selecting all of them as vertices would make the interior angle at point \(B\) exactly \(180\) degrees, violating the condition. In this case, by excluding the middle point \(B\) and selecting only \(A, C\), we can prevent the interior angle from becoming \(180\) degrees without reducing the area.

Therefore, when computing the convex hull, we need to perform the process of “removing the middle point when three points are collinear.”

Algorithm

The solution code in this editorial uses Andrew’s Monotone Chain Algorithm, a well-known efficient algorithm for computing the convex hull.

Step 1: Sorting the Points

Sort all points in ascending order of \(x\)-coordinate (breaking ties by ascending \(y\)-coordinate). This allows us to process points sequentially from the leftmost to the rightmost.

Step 2: Building the Convex Hull (Lower and Upper)

The convex hull is built in two parts: the “lower” hull and the “upper” hull.

1. Building the lower hull: Add the sorted points from left to right into a stack (array). When adding a new point \(p\), use the cross product to determine the positional relationship between the last two points \(a, b\) in the stack and \(p\). If the rotation direction from vector \(\vec{ab}\) to \(\vec{bp}\) is clockwise, or the points are collinear (cross product is \(0\) or less), then the previous point \(b\) is not suitable as a convex hull vertex (the interior angle would be \(180\) degrees or more, or the points are collinear), so we remove it from the stack (pop). This check is repeated until the condition is satisfied, then point \(p\) is added.

2. Building the upper hull: Process the points from right to left (in reverse order) and perform the same procedure to build the upper boundary.

Step 3: Computing the Area

Combine the lower and upper hulls to obtain the convex hull vertices \(p_0, p_1, \ldots, p_{k-1}\) arranged in counterclockwise order. Apply the Shoelace formula (polygon area formula) to this vertex sequence. Given vertices \(p_i = (x_i, y_i)\), twice the area \(2S\) is computed as follows:

\[2S = \left| \sum_{i=0}^{k-1} (x_i y_{i+1} - x_{i+1} y_i) \right| \quad (\text{where } p_k = p_0)\]

Since all coordinates are integers, this computation can be performed entirely with integer types without using any floating-point arithmetic.

Complexity

• Time Complexity: \(O(N \log N)\)

  • Sorting the points takes \(O(N \log N)\).
  • Building the convex hull (Monotone Chain method): each point is added to the stack at most once and removed at most once, so this takes \(O(N)\).
  • Computing the area takes \(O(k)\) for \(k \le N\) convex hull vertices.
  • Therefore, the overall time complexity is \(O(N \log N)\), dominated by the sorting step. This runs sufficiently fast (approximately 0.2 seconds) for \(N = 2 \times 10^5\).

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used for the array storing point information and the stack holding the convex hull.

Implementation Notes

• Excluding collinear points: In the cross product computation, normally we use cross < 0 (excluding only clockwise turns), but since we also want to exclude collinear points (cross product equals 0), we use the <= inequality.

  # Cross product of a, b, p. If <= 0, the points are collinear or clockwise, so remove b
  if (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) <= 0:
    lower.pop()
  

• Preventing duplicate endpoints: When combining the lower and upper hulls, the first and last points (the leftmost and rightmost points) are duplicated, so we use lower[:-1] + upper[:-1] to remove the duplicates when merging.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    points = []
    idx = 1
    for _ in range(N):
        points.append((int(input_data[idx]), int(input_data[idx+1])))
        idx += 2
    
    points.sort()
    
    # Andrew's Monotone Chain Algorithm
    lower = []
    for p in points:
        while len(lower) >= 2:
            a = lower[-2]
            b = lower[-1]
            if (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) <= 0:
                lower.pop()
            else:
                break
        lower.append(p)
        
    upper = []
    for p in reversed(points):
        while len(upper) >= 2:
            a = upper[-2]
            b = upper[-1]
            if (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) <= 0:
                upper.pop()
            else:
                break
        upper.append(p)
        
    hull = lower[:-1] + upper[:-1]
    
    ans = 0
    k = len(hull)
    for i in range(k):
        p1 = hull[i]
        p2 = hull[(i + 1) % k]
        ans += p1[0] * p2[1] - p2[0] * p1[1]
        
    print(abs(ans))

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.