(WIP) 最大面積の凸多角形は \((X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)\) の凸包です。この凸角形の頂点となるような点は \(N\) 本の杭の中に必ず存在するため、これらのみを選んで狭義の凸角形をなすことができます。

点の集合に対する凸包を求めるアルゴリズムは様々ですが、競技プログラミングにおいてはMonotone Chainというアルゴリズムが特に有名です。概要としては \(x\) 座標の小さい順に頂点をソートし、その順に走査して上側凸包、逆順に走査して下側凸包を求めるといったアルゴリズムです。こうすることで、反時計回りの順番で凸包の頂点を列挙できます。ここではソートがボトルネックとなり、時間計算量は \(\mathrm{O}(N\log N)\) です。

また、実際に答えとなる面積は求めた反時計回りに並んだ凸包の頂点を順に隣合う頂点の外積を総和を取ることで求められます。これは時間計算量 \(\mathrm{O}(N)\) で計算できます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
pair<int, int> operator-(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    return pair<int, int>{lhs.first - rhs.first, lhs.second - rhs.second};
}
long long cross(pair<int, int> l, pair<int, int> r) {
    return (long long)l.first * r.second - (long long)l.second * r.first;
}
int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> xy(n);
    for (int i = 0; i < n; ++i) cin >> xy[i].first >> xy[i].second;
    sort(xy.begin(), xy.end());
    vector<pair<int, int>> ch;
    int k = 0;
    for (int i = 0; i < n; ch.emplace_back(xy[i++]), k++) {
        while (k >= 2 && cross(ch[k - 1] - ch[k - 2], xy[i] - ch[k - 1]) <= 0) ch.pop_back(), --k;
    }
    for (int i = n - 2, t = k + 1; i >= 0; ch.emplace_back(xy[i--]), k++) {
        while (k >= t && cross(ch[k - 1] - ch[k - 2], xy[i] - ch[k - 1]) <= 0) ch.pop_back(), --k;
    }
    ch.pop_back();
    k--;
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        ans += cross(ch[i], ch[(i + 1) % k]);
    }
    cout << ans << endl;
}