概要

与えられた \(N\) 個の点からいくつかの点を選んで作れる狭義の凸多角形のうち、面積が最大となるものを探し、その面積の \(2\) 倍の値を求める問題です。

考察

面積を最大化するためには、できるだけ外側にある点を選んで大きく囲む必要があります。これは、与えられたすべての点を内包する「凸包（Convex Hull）」を求めることに他なりません。

素朴なアプローチとして、すべての点の組み合わせ（部分集合）を試して多角形を作り、面積を計算する方法が考えられます。しかし、この方法では点の選び方が \(O(2^N)\) 通りとなり、\(N \le 2 \times 10^5\) という大きな制約では到底制限時間に間に合いません（TLEになります）。したがって、効率的に凸包を求めるアルゴリズムが必要です。

また、問題文の「狭義の凸多角形」という条件から、凸多角形の辺上にある点（内角が \(180\) 度になる点）は選んではいけないことに注意する必要があります。

アルゴリズム

Monotone Chain（モノトーンチェーン）アルゴリズムを用いて凸包を求めます。

1. 点のソート: まず、すべての点を \(x\) 座標の昇順にソートします（\(x\) 座標が同じ場合は \(y\) 座標の昇順）。
2. 下側凸包の構築: ソートした点を順番に見ていき、下半分の輪郭（下側凸包）を作ります。新しい点 \(C\) を追加する際、直近の \(3\) 点 \(A, B, C\) が「反時計回り（左回り）」になっているかを外積を使って判定します。もし時計回りや一直線上になっていれば、条件を満たすまで直前の点 \(B\) を削除します。
3. 上側凸包の構築: 今度は点を逆順（右から左）に見ていき、同様の手順で上半分の輪郭（上側凸包）を作ります。
4. 面積の計算: 下側凸包と上側凸包を結合して全体の凸包を得ます。得られた凸包の頂点集合に対して、「多角形の面積の公式（Shoelace formula / 測量士の公式）」を適用します。頂点が \((x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)\) の順に並んでいるとき、面積の \(2\) 倍は \(\sum_{i=1}^k (x_i y_{i+1} - x_{i+1} y_i)\) の絶対値として計算できます（ただし \(x_{k+1}=x_1, y_{k+1}=y_1\) とします）。

計算量

• 時間計算量: \(O(N \log N)\) 点のソートに \(O(N \log N)\) かかります。凸包の構築や面積の計算では、各点がリストに「追加」される回数と「削除」される回数がそれぞれ高々 \(1\) 回であるため、ならし計算量で \(O(N)\) となります。全体として \(O(N \log N)\) で非常に高速です。
• 空間計算量: \(O(N)\) 入力された座標のリストや、凸包を構成する頂点を保存するためのリストに比例するメモリを使用します。

実装のポイント

• 外積による判定と「狭義の」条件: 点 \(A = (ax, ay)\)、点 \(B = (bx, by)\)、点 \(C = (cx, cy)\) について、ベクトル \(AB\) とベクトル \(AC\) の外積は (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) で計算できます。 この値が正であれば反時計回り、\(0\) であれば一直線上、負であれば時計回りを意味します。コード内で <=（\(0\) 以下）のときに点 \(B\) を削除する条件にすることで、内角が \(180\) 度になる辺上の点（一直線上の点）を自動的に排除でき、「狭義の凸多角形」という条件を簡単に満たすことができます。

• 整数での計算による誤差回避: 座標がすべて整数で与えられるため、外積の判定や面積の \(2\) 倍の計算において割り算（浮動小数点数）を使う必要がありません。すべて整数型で計算することで、小数の丸め誤差による不正解（WA）を完全に防ぐことができます。

  ソースコード

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()

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