概要

\(N\) 本の杭から3本以上を選び、選んだ杭を頂点とする狭義の凸多角形（すべての内角が180度未満）の面積を最大化する問題です。答えは全点の凸包（共線点を除いた厳密な凸包）の面積に等しくなります。

考察

重要な気づき1: 最大面積の凸多角形は凸包

選んだ杭が作る凸多角形は、全ての杭の凸包（convex hull）の内部または境界上に必ず含まれます。これは凸包の定義から明らかです。

したがって、面積を最大化するには凸包そのものを選べばよいということになります。凸包に含まれない内部の点を追加しても面積は増えません。

重要な気づき2: 共線点の扱い

凸包の辺上に別の杭が存在する場合、その杭を頂点として選んでしまうと内角が180度になり、「狭義の凸多角形」の条件に違反します。

しかし、この問題では杭を「選ぶ」ことが自由なので、辺上の点を選ばなければよいだけです。辺上の点を除いても多角形の形（＝面積）は変わりません。

素朴なアプローチが不要な理由

全ての部分集合を試すと \(O(2^N)\) で到底間に合いませんが、上記の考察により凸包を求めるだけで解けます。

アルゴリズム

1. 凸包の計算: Andrew’s Monotone Chain アルゴリズムを使います。外積（cross product）の値が \(\leq 0\) の点を除去することで、共線点（3点が一直線上にある場合の中間の点）を自動的に除外し、厳密な凸包（狭義の凸多角形）が得られます。

2. 面積の計算: Shoelace formula（靴紐公式）を用いて凸包の面積を計算します。凸包の頂点を \((x_0, y_0), (x_1, y_1), \ldots, (x_{h-1}, y_{h-1})\) とすると： $\(2S = \left| \sum_{i=0}^{h-1} (x_i \cdot y_{(i+1) \bmod h} - x_{(i+1) \bmod h} \cdot y_i) \right|\)$

3. 出力: \(2S\) を整数として出力します。

計算量

• 時間計算量: \(O(N \log N)\)（凸包計算のソートがボトルネック）
• 空間計算量: \(O(N)\)（点の格納と凸包の格納）

実装のポイント

• 凸包で <= 0 を使う理由: cross(o, a, b) <= 0 で判定することにより、外積が0（＝3点が共線）の場合も中間の点を除去します。これにより得られる凸包は常に狭義の凸多角形になります。もし < 0 を使うと共線点が残り、狭義の条件を満たさなくなります。

• 座標が最大 \(10^9\): 外積の計算で最大 \(2 \times 10^{18}\) 程度の値になりますが、Python は多倍長整数を扱えるのでオーバーフローの心配はありません。

• Shoelace formula の結果は常に整数: 座標が整数のとき \(2S\) は整数になることが保証されているため、浮動小数点演算は不要です。

  ソースコード

import sys
from functools import cmp_to_key

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):
    points = sorted(set(points))
    n = len(points)
    if n <= 1:
        return points
    
    # Build lower hull
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    
    # Build upper hull
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    
    # Concatenation of the lower and upper hulls gives the convex hull.
    # Last point of each half is omitted because it is repeated.
    return lower[:-1] + upper[:-1]

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    points = []
    for i in range(n):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        points.append((x, y))
    
    hull = convex_hull(points)
    h = len(hull)
    
    if h <= 2:
        # This shouldn't happen given constraints
        print(0)
        return
    
    # Now we need to find the maximum area strictly convex polygon using subset of hull points.
    # The convex hull itself is strictly convex (our convex_hull function uses strict inequality,
    # so no three collinear points on hull). Wait, let me check: we use cross(...) <= 0,
    # which means we remove collinear points. So the hull is strictly convex.
    
    # Actually, with cross <= 0, we remove points that are collinear, so the resulting hull
    # is strictly convex. The area of this hull is the maximum.
    
    # But wait - we need to be more careful. The problem says we need a strictly convex polygon
    # where all selected points are vertices. The convex hull of all points gives the maximum
    # area convex polygon, BUT only if the hull is strictly convex (no three consecutive 
    # collinear points). Our implementation already ensures this by using <= 0 (strict).
    
    # However, there could be input points that lie ON the edges of the convex hull but are
    # not vertices of our strict hull. Those points are simply not selected, which is fine.
    # The issue would be if we MUST select them, but we don't - we choose which points to select.
    
    # So the answer is simply the area of the strictly convex hull.
    
    # Compute 2 * area using shoelace formula
    area2 = 0
    for i in range(h):
        j = (i + 1) % h
        area2 += hull[i][0] * hull[j][1]
        area2 -= hull[j][0] * hull[i][1]
    
    area2 = abs(area2)
    print(area2)

solve()

この解説は claude4.6opus-thinking によって生成されました。