Overview

Given \(N\) points, the problem asks to select 3 or more points and form a “strictly convex polygon” with them as vertices, then find the maximum area (multiplied by 2).

This problem reduces to finding the Convex Hull of the given point set and computing its area.

---

Analysis

1. How to Maximize the Area?

Intuitively, the larger the polygon we choose, the greater the area becomes. The smallest convex polygon that encloses all points in a point set on the plane is called the convex hull. No matter what convex polygon is formed from the original point set, its area cannot exceed the area of the “overall convex hull.” Therefore, selecting the convex hull itself is the optimal strategy for maximizing the area.

2. The “Strictly Convex Polygon” Condition

The problem statement has the constraint that “all interior angles must be less than 180 degrees.” This means that if there are points lying on the boundary (on the edges) of the convex hull other than vertices, they must not be selected as vertices of the polygon. For example, when 3 points are collinear, if the middle point is selected, the interior angle at that point becomes exactly 180 degrees.

Therefore, when constructing the convex hull, we need to perform the process of “removing interior points among 3 collinear points.”

3. Limitations of the Naive Approach

Exploring all combinations of points (\(2^N\) possibilities) would result in a Time Limit Exceeded (TLE) under the constraint \(N \le 2 \times 10^5\). By using an efficient convex hull algorithm (such as the Monotone Chain method), the problem can be solved in \(O(N \log N)\) time for sorting the points and \(O(N)\) time for constructing the convex hull.

---

Algorithm

This problem can be solved in the following 3 steps.

Step 1: Sorting the Points

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

Step 2: Constructing the Convex Hull (Monotone Chain Method)

For the sorted point set, compute the Lower Hull and Upper Hull separately, then combine them.

1. Constructing the Lower Hull: Starting from the leftmost point, add points to a stack sequentially. When adding a new point \(P\), check the positional relationship (cross product) between the last two points \(A, B\) on the stack and \(P\). If the rotation direction from vector \(\vec{AB}\) to \(\vec{BP}\) is not counterclockwise (i.e., it turns right or is collinear, meaning the cross product is less than or equal to 0), then the previous point \(B\) cannot be a vertex of the convex hull (or is an unnecessary point on the boundary), so it is removed from the stack (popped). This operation is repeated until the turn becomes counterclockwise, and then point \(P\) is added.
2. Constructing the Upper Hull: Perform the same process in reverse order starting from the rightmost point.
3. Combining: Combine the Lower Hull and Upper Hull (removing duplicate endpoints).

By setting the cross product condition to cross_product <= 0, we reliably exclude collinear points (where the cross product equals 0), extracting only the vertices of the “strictly convex polygon.”

Step 3: Computing the Area

Using the obtained set of convex hull vertices, compute twice the polygon’s area using the Shoelace formula. When there are \(k\) vertices arranged counterclockwise as \((x_0, y_0), (x_1, y_1), \dots, (x_{k-1}, y_{k-1})\), twice the area (\(2S\)) is given by the following formula:

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

---

Complexity

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

  • Sorting the points takes \(O(N \log N)\) time.
  • Constructing the convex hull (Monotone Chain method) takes \(O(N)\) time, since each point is added to the stack at most once and removed at most once.
  • Computing the area takes \(O(N)\) time.
  • Overall, sorting is the bottleneck, and the algorithm runs in \(O(N \log N)\). This is sufficiently fast for \(N = 2 \times 10^5\).

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

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

---

Implementation Notes

1. Preventing Overflow: Since the maximum coordinate value is \(10^9\), the cross product and area computations may involve values exceeding \(10^{18}\) (up to approximately \(4 \times 10^{18}\)). While C++’s long long type (maximum approximately \(9 \times 10^{18}\)) can barely accommodate this, using the 128-bit integer type __int128 for calculations completely prevents overflow for safety.

2. Outputting __int128: C++’s std::cout does not natively support outputting __int128. Therefore, a custom output routine is used that divides the value by 10 to convert each digit to a character, then reverses the string for output.

   Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct Point {
    long long x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// OからA、Bへのベクトルの外積の符号
// OA x OB = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)
int cross_product(const Point& O, const Point& A, const Point& B) {
    __int128 val = (__int128)(A.x - O.x) * (B.y - O.y) - (__int128)(A.y - O.y) * (B.x - O.x);
    if (val > 0) return 1;
    if (val < 0) return -1;
    return 0;
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }

    // X座標、次いでY座標でソート
    sort(points.begin(), points.end());

    // 下側凸包の構築
    vector<Point> lower;
    for (const auto& p : points) {
        while (lower.size() >= 2 && cross_product(lower[lower.size() - 2], lower.back(), p) <= 0) {
            lower.pop_back();
        }
        lower.push_back(p);
    }

    // 上側凸包の構築
    vector<Point> upper;
    for (auto it = points.rbegin(); it != points.rend(); ++it) {
        const auto& p = *it;
        while (upper.size() >= 2 && cross_product(upper[upper.size() - 2], upper.back(), p) <= 0) {
            upper.pop_back();
        }
        upper.push_back(p);
    }

    // 重複する端点を除去して結合
    lower.pop_back();
    upper.pop_back();
    vector<Point> hull = lower;
    hull.insert(hull.end(), upper.begin(), upper.end());

    // 面積の2倍を計算
    __int128 double_area = 0;
    int k = hull.size();
    for (int i = 0; i < k; ++i) {
        Point p1 = hull[i];
        Point p2 = hull[(i + 1) % k];
        double_area += (__int128)p1.x * p2.y - (__int128)p2.x * p1.y;
    }

    if (double_area < 0) {
        double_area = -double_area;
    }

    // __int128 の出力
    if (double_area == 0) {
        cout << 0 << "\n";
    } else {
        string s;
        while (double_area > 0) {
            s += (char)('0' + (double_area % 10));
            double_area /= 10;
        }
        reverse(s.begin(), s.end());
        cout << s << "\n";
    }

    return 0;
}

---

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