概要

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

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

考察

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

平面上の点集合からいくつかの点を選んで凸多角形を作るとき、その面積を最大にするには、できるだけ「外側」にある点を選ぶべきです。 与えられたすべての点を囲む最小の凸多角形を凸包と呼びます。凸包の内部や境界上にある任意の点を取り込んでも、凸包そのものの面積より大きくなることはありません。したがって、面積を最大化するためには、全体の凸包の頂点となる点を選べばよいことになります。

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

問題文には「すべての内角が180度未満」という条件（狭義の凸多角形）があります。これは、凸多角形の辺上に頂点以外の点が存在してはならないことを意味します。

例えば、一直線上に \(3\) つの点 \(A, B, C\) がこの順に並んでいるとき、これらすべてを頂点として選ぶと、点 \(B\) における内角が \(180\) 度になってしまい、条件を満たしません。この場合、途中の点 \(B\) を除外して \(A, C\) のみを選ぶことで、面積を減らすことなく、かつ内角が \(180\) 度になるのを防ぐことができます。

したがって、凸包を求める際に「3点が一直線上に並ぶ場合、真ん中の点を取り除く」という処理を行う必要があります。

アルゴリズム

本稿の正解コードでは、凸包を効率的に求める代表的なアルゴリズムである Andrew’s Monotone Chain Algorithm（モノトーンチェーン法） を使用しています。

ステップ 1: 点のソート

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

ステップ 2: 凸包の構築（下側と上側）

凸包を「下側（lower）」と「上側（upper）」の2つに分けて構築します。

1. 下側凸包の構築: ソートされた点を左から順にスタック（配列）に追加していきます。 新しく点 \(p\) を追加する際、スタックの末尾の2点 \(a, b\) と \(p\) の位置関係を外積を用いて判定します。 ベクトル \(\vec{ab}\) から \(\vec{bp}\) への回転方向が時計回り、または一直線上にある場合（外積が \(0\) 以下の場合）、直前の点 \(b\) は凸包の頂点にふさわしくない（内角が \(180\) 度以上になる、または一直線上に並ぶ）ため、スタックから取り除きます（pop）。この判定を条件を満たすまで繰り返したあと、点 \(p\) を追加します。

2. 上側凸包の構築: 点を右から左（逆順）に見ていき、同様の処理を行って上側の境界を構築します。

ステップ 3: 面積の計算

得られた下側凸包と上側凸包を結合して、反時計回りに並んだ凸包の頂点列 \(p_0, p_1, \ldots, p_{k-1}\) を得ます。 この頂点列に対して、シューレース公式（多角形の面積公式）を適用します。 頂点 \(p_i = (x_i, y_i)\) としたとき、面積の2倍 \(2S\) は以下の式で求められます。

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

座標はすべて整数であるため、この計算は小数を一切使わずに整数型のみで行うことができます。

計算量

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

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

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

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

実装のポイント

• 一直線上の点の排除: 外積の計算において、通常は cross < 0（時計回りのみ排除）としますが、今回は一直線上にある点（外積が 0）も排除したいため、不等号を <= にしています。

  # a, b, p の外積。0以下なら一直線上、または時計回りなので b を取り除く
  if (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) <= 0:
    lower.pop()
  

• 端点の重複防止: 下側凸包と上側凸包を結合する際、最初と最後の点（最も左の点と最も右の点）が重複するため、lower[:-1] + upper[:-1] として重複を除いて結合しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    points = []
    idx = 1
    for _ in range(N):
        points.append((int(input_data[idx]), int(input_data[idx+1])))
        idx += 2
    
    points.sort()
    
    # Andrew's Monotone Chain Algorithm
    lower = []
    for p in points:
        while len(lower) >= 2:
            a = lower[-2]
            b = lower[-1]
            if (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) <= 0:
                lower.pop()
            else:
                break
        lower.append(p)
        
    upper = []
    for p in reversed(points):
        while len(upper) >= 2:
            a = upper[-2]
            b = upper[-1]
            if (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]) <= 0:
                upper.pop()
            else:
                break
        upper.append(p)
        
    hull = lower[:-1] + upper[:-1]
    
    ans = 0
    k = len(hull)
    for i in range(k):
        p1 = hull[i]
        p2 = hull[(i + 1) % k]
        ans += p1[0] * p2[1] - p2[0] * p1[1]
        
    print(abs(ans))

if __name__ == '__main__':
    solve()

---

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