概要

与えられた \(N\) 個の点から 3 つ以上の点を選び、それらを頂点とする「狭義の凸多角形」を作るとき、その面積の最大値（の 2 倍）を求める問題です。

この問題は、与えられた点集合の凸包（Convex Hull）を求め、その凸包の面積を計算することに帰着されます。

---

考察

1. 面積を最大化するには？

直感的に、選ぶ多角形を大きくすればするほど面積は広くなります。平面上の点集合をすべて囲む最小の凸多角形を凸包と呼びます。 元の点集合からどのような凸多角形を作ったとしても、その面積は「全体の凸包」の面積を超えることはできません。したがって、全体の凸包そのものを選択することが、面積を最大化するための最適な戦略となります。

2. 「狭義の凸多角形」の条件

問題文には「すべての内角が 180 度未満」という制約があります。これは、凸包の境界上（辺の上）に頂点以外の点が乗っている場合、それらを多角形の頂点として選んではいけないことを意味します。 例えば、3 点が一直線上に並んでいるとき、真ん中の点を選んでしまうと、その点での内角が 180 度になってしまいます。

したがって、凸包を構築する際に「一直線上に並ぶ 3 点のうち、内側の点を除去する」という処理を行う必要があります。

3. 素朴なアプローチの限界

すべての点の組み合わせ（\(2^N\) 通り）を探索することは、\(N \le 2 \times 10^5\) という制約のもとでは実行時間制限（TLE）になります。 凸包を効率的に求めるアルゴリズム（モノトーンチェーン法など）を使用すれば、点のソートに \(O(N \log N)\)、凸包の構築に \(O(N)\) の時間で解くことが可能です。

---

アルゴリズム

本問題は以下の 3 ステップで解くことができます。

ステップ 1: 点のソート

すべての点を \(x\) 座標の昇順（\(x\) 座標が同じなら \(y\) 座標の昇順）でソートします。これにより、左から右へ順番に点を走査できるようになります。

ステップ 2: 凸包の構築（モノトーンチェーン法）

ソートされた点集合に対して、下側凸包（Lower Hull）と上側凸包（Upper Hull）をそれぞれ求め、最後に結合します。

1. 下側凸包の構築: 左端の点から順にスタックに追加していきます。新しい点 \(P\) を追加する際、スタックの末尾 2 点 \(A, B\) と \(P\) の位置関係（外積）を確認します。 ベクトル \(\vec{AB}\) から \(\vec{BP}\) への回転方向が反時計回りでない（右折または一直線上、すなわち外積が 0 以下）場合、直前の点 \(B\) は凸包の頂点になり得ない（または境界上の不要な点である）ため、スタックから取り除きます（ポップ）。この操作を反時計回りになるまで繰り返したのち、点 \(P\) を追加します。
2. 上側凸包の構築: 右端の点から逆順に同様の処理を行います。
3. 結合: 下側凸包と上側凸包を結合します（重複する端点は除きます）。

外積の条件を cross_product <= 0 とすることで、一直線上に並ぶ点（外積が 0 になる点）を確実に排除し、「狭義の凸多角形」の頂点のみを抽出できます。

ステップ 3: 面積の計算

得られた凸包の頂点集合を用いて、靴紐の公式（Shoelace formula）により多角形の面積の 2 倍を計算します。 頂点数が \(k\) 個で、反時計回りに \((x_0, y_0), (x_1, y_1), \dots, (x_{k-1}, y_{k-1})\) と並んでいるとき、面積の 2 倍（\(2S\)）は以下の式で求まります。

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

---

計算量

• 時間計算量: \(O(N \log N)\)

  • 点のソートに \(O(N \log N)\) 時間かかります。
  • 凸包の構築（モノトーンチェーン法）は、各点がスタックに高々 1 回追加され、高々 1 回取り除かれるため \(O(N)\) 時間です。
  • 面積の計算は \(O(N)\) 時間です。
  • 全体としてソートがボトルネックとなり、\(O(N \log N)\) で動作します。これは \(N = 2 \times 10^5\) に対して十分高速に動作します。

• 空間計算量: \(O(N)\)

  • 点の情報を格納する配列や、凸包の頂点を格納するスタックに \(O(N)\) のメモリを使用します。

---

実装のポイント

1. オーバーフローの防止: 座標の最大値が \(10^9\) であるため、外積の計算や面積の計算の過程で \(10^{18}\) を超える値（最大で約 \(4 \times 10^{18}\)）を扱うことになります。 C++の long long 型（最大約 \(9 \times 10^{18}\)）でもギリギリ収まりますが、安全のために 128 ビット整数型である __int128 を使用して計算を行うことで、オーバーフローを完全に防ぐことができます。

2. __int128 の出力: C++の std::cout は標準で __int128 の出力に対応していません。そのため、値を 10 で割りながら各桁を文字に変換し、文字列を反転させて出力する自作の出力処理を行っています。

   ソースコード

#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;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。