概要

\(N\) 個の凸図形から空でない部分集合を選び、そのミンコフスキー和が面積正の凸多角形になる部分集合の個数を求める問題です。余事象（面積が正にならない場合）を数えて全体から引く方針で解きます。

考察

ミンコフスキー和と図形の種類

ミンコフスキー和の性質を整理します。

• 点のミンコフスキー和は単なる平行移動なので、点をいくつ足しても図形の「形」は変わりません。
• 線分同士のミンコフスキー和は、方向が同じなら長い線分（1次元のまま）、方向が異なれば平行四辺形（面積正の凸多角形）になります。
• 凸多角形（面積正）が1つでも含まれていれば、ミンコフスキー和は必ず面積正の凸多角形になります（面積は減らない）。

面積が正にならない「悪い」部分集合の条件

ミンコフスキー和が凸多角形にならない（点または線分にしかならない）条件は：

1. 凸多角形が1つも選ばれていない（凸多角形を1つでも含めると面積正が確定する）
2. 選ばれた線分がすべて同一方向である（異なる方向の線分が2本以上あると平行四辺形ができて面積正になる）

つまり「悪い」部分集合は以下のいずれかです： - 点のみからなる部分集合（\(2^{\text{num\_points}} - 1\) 通り） - 点と、ある1つの方向の線分のみからなる部分集合（各方向ごとに数える）

余事象で数える

\[\text{答え} = (2^N - 1) - (\text{悪い部分集合の数})\]

悪い部分集合の数は：

\[\text{bad} = (2^{P} - 1) + \sum_{d} 2^{P} \cdot (2^{c_d} - 1)\]

ここで \(P\) は点の個数、\(c_d\) は方向 \(d\) の線分の個数です。第1項は「点のみ」、第2項は「点（0個以上）＋方向 \(d\) の線分（1本以上）」の場合です。

アルゴリズム

1. 各凸図形を点・線分・凸多角形に分類する。
   • 頂点がすべて同一点 → 点
   • 頂点がすべて同一直線上 → 線分（方向を正規化して記録）
   • それ以外 → 凸多角形
2. 線分の方向を正規化する：方向ベクトル \((dx, dy)\) を \(\gcd\) で割り、符号を統一（先頭の非零成分が正になるように）。
3. 方向ごとの線分の個数を集計する。
4. 余事象の公式で答えを計算する。

計算量

• 時間計算量: \(O(\sum K_i + D)\)（\(D\) は異なる方向の数、最大 \(N\)）
  • 各図形の分類に \(O(K_i)\)、集計と計算に \(O(N)\)
• 空間計算量: \(O(\sum K_i + N)\)

実装のポイント

• 同一直線上の判定: 最初の2つの異なる点を基準に、残りの全点との外積が0かどうかで判定します。

• 方向の正規化: 線分の方向ベクトル \((dx, dy)\) を \(\gcd(|dx|, |dy|)\) で割り、「\(dx > 0\)」または「\(dx = 0\) かつ \(dy > 0\)」となるように符号を統一します。これにより同じ直線方向を持つ線分を同一グループにまとめられます。

• \(K_i \geq 3\) で全頂点が同一直線上の場合、問題文の定義により線分として扱う必要があります。コード中では重複頂点の除去後に共線性を判定しています。

• pow(2, n, MOD) を用いた高速べき乗で \(\bmod\) 計算を行います。

  ソースコード

import sys
from collections import defaultdict
from math import gcd

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    MOD = 10**9 + 7
    
    N = int(input_data[idx]); idx += 1
    
    num_points = 0
    num_polygons = 0
    direction_counts = defaultdict(int)
    
    for _ in range(N):
        K = int(input_data[idx]); idx += 1
        pts = []
        for j in range(K):
            x = int(input_data[idx]); idx += 1
            y = int(input_data[idx]); idx += 1
            pts.append((x, y))
        
        # Compute convex hull to determine the type
        # But per problem statement, if K>=3 and not collinear, it's already a convex polygon
        # We need to check if the figure is a point, segment, or polygon
        
        # Collect unique points
        unique = list(set(pts))
        
        if len(unique) == 1:
            num_points += 1
            continue
        
        # Check if all points are collinear
        # Use cross product check with first two distinct points
        p0 = unique[0]
        p1 = unique[1]
        collinear = True
        for i in range(2, len(unique)):
            cross = (p1[0]-p0[0])*(unique[i][1]-p0[1]) - (p1[1]-p0[1])*(unique[i][0]-p0[0])
            if cross != 0:
                collinear = False
                break
        
        if not collinear:
            num_polygons += 1
        else:
            # It's a segment - find direction
            dx = p1[0] - p0[0]
            dy = p1[1] - p0[1]
            # Normalize direction
            g = gcd(abs(dx), abs(dy))
            dx //= g
            dy //= g
            # Canonical form: make first nonzero positive
            if dx < 0 or (dx == 0 and dy < 0):
                dx, dy = -dx, -dy
            direction_counts[(dx, dy)] += 1
    
    num_segments_total = sum(direction_counts.values())
    
    total = pow(2, N, MOD) - 1
    
    # Bad subsets: no polygon, and all segments from at most one direction
    # All points only
    bad = pow(2, num_points, MOD) - 1
    
    # Points + segments from exactly one direction group
    p2np = pow(2, num_points, MOD)
    for d, cnt in direction_counts.items():
        bad = (bad + p2np * (pow(2, cnt, MOD) - 1)) % MOD
    
    ans = (total - bad) % MOD
    print(ans)

solve()

---

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