概要

「どの部分集合のミンコフスキー和が面積正の凸多角形になるか」を直接判定するのではなく、逆に「点または線分にしかならない部分集合」を数えて全体から引く問題です。
鍵は、ミンコフスキー和が退化（点/線分）のままでいる条件を、図形の種類と線分の向きで分類して数え上げることです。

考察

まず、各図形は次の3種類に分類できます。

1. 点
2. 線分（\(K=2\)、または \(K\ge3\) でも全点が一直線）
3. 真の凸多角形（面積正）

重要な性質1：1つでも真の凸多角形が入ると結果は凸多角形

ミンコフスキー和は「次元が下がらない」ので、2次元図形（面積正の凸多角形）を1つでも含めば、和も2次元です。
したがって退化（点/線分）になるのは、点と線分だけを選んだときに限られます。

重要な性質2：線分どうしの向き

• 同じ向き（平行）な線分だけを足す → 結果は同じ向きの線分
• 異なる向きの線分を2本以上足す → 結果は2次元になり凸多角形

つまり、点と線分だけの世界で退化を保つには、 - 線分を1方向グループからしか選ばない（0本でも可） - 点はいくつ選んでもよい（平行移動にしかならない）

なぜ素朴法が無理か

部分集合は \(2^N-1\) 通りで、\(N\le 5\times10^4\) なので全探索は不可能です。
そこで「方向ごとの個数」を使った組合せ計算に落とし込みます。

---

点の個数を \(m_{\text{point}}\)、線分の個数を \(m_{\text{seg}}\) とし、
線分方向グループ \(d\) ごとの本数を \(c_d\)（グループ数 \(D\)）とします。

点と線分のみからなる部分集合で、退化なもの（空集合含む）は：

• 点だけ選ぶ場合：\(2^{m_{\text{point}}}\)
• 線分をちょうど1方向グループから選ぶ場合：
  各 \(d\) について \((2^{c_d}-1)\) 通り（空でない選び方）、点は自由で \(2^{m_{\text{point}}}\) 倍

よって [ \text{deg_no_poly} =2^{m_{\text{point}}}\left(1+\sum_d(2^{cd}-1)\right) =2^{m{\text{point}}}\left(\sum_d2^{c_d}-D+1\right) ]

全体の部分集合数（空含む）は \(2^N\)。
「凸多角形になる非空部分集合数」は、実は [ 2^N-\text{deg_no_poly} ] でよいです（空集合は退化側にのみ含まれるため、この式でちょうど打ち消し合う）。

アルゴリズム

1. 全図形を読む。
2. 各図形について：
   • \(K=1\) なら点カウント。
   • それ以外は「全点が一直線か」を外積で判定。
   • 一直線でなければ真の凸多角形（個数としては直接使わない）。
   • 一直線なら線分として扱い、端点差分ベクトルを既約化して向きキーにする：
     • \((dx,dy)\) を \(\gcd\) で割る
     • 符号を正規化（\(dx<0\) または \(dx=0,dy<0\) なら反転）
     • 垂直・水平も同様に一意化
   • その向きのグループ数を加算。
3. 式 [ \text{deg_no_poly} =2^{m_{\text{point}}}\left(\sum_d2^{c_d}-D+1\right)\pmod{M} ] を計算。
4. 答え [ \text{ans}=2^N-\text{deg_no_poly}\pmod{M} ] を出力。

計算量

• 時間計算量: \(O\!\left(\sum K_i\right)\)
  （各図形の共線判定を1回ずつ）
• 空間計算量: \(O(D)\)
  （方向グループのハッシュマップ）

実装のポイント

• 共線判定は基準2点 \((x_0,y_0),(x_1,y_1)\) に対し、各点で外積 [ (x_1-x_0)(y-y_0)-(y_1-y_0)(x-x_0) ] が 0 かで判定。

• \(K\ge3\) で全点共線のとき、問題文保証により端点は先頭・末尾を使ってよい。

• 向きの正規化をしないと、同一直線方向でも \((1,2)\) と \((-1,-2)\) が別扱いになって WA になります。

• 最後は必ず \(\bmod (10^9+7)\) で負値を補正して出力します。

  ソースコード

import sys

MOD = 10**9 + 7

def main():
    input = sys.stdin.readline
    N = int(input())

    m_point = 0
    m_seg = 0
    dir_count = {}

    for _ in range(N):
        k = int(input())
        pts = [tuple(map(int, input().split())) for _ in range(k)]

        if k == 1:
            m_point += 1
            continue

        # check if all collinear
        x0, y0 = pts[0]
        x1, y1 = pts[1]
        dx0 = x1 - x0
        dy0 = y1 - y0

        col = True
        for i in range(2, k):
            x, y = pts[i]
            if dx0 * (y - y0) - dy0 * (x - x0) != 0:
                col = False
                break

        if not col:
            # true 2D convex polygon
            continue

        # degenerate: segment (k>=2 collinear) or k==2
        if k >= 2:
            if k == 2:
                ax, ay = pts[0]
                bx, by = pts[1]
            else:
                # by problem statement for collinear k>=3, endpoints are first and last
                ax, ay = pts[0]
                bx, by = pts[-1]

            dx = bx - ax
            dy = by - ay
            # non-zero guaranteed by distinct vertices
            if dx == 0:
                ux, uy = 0, 1
            elif dy == 0:
                ux, uy = 1, 0
            else:
                import math
                g = math.gcd(abs(dx), abs(dy))
                dx //= g
                dy //= g
                if dx < 0 or (dx == 0 and dy < 0):
                    dx = -dx
                    dy = -dy
                ux, uy = dx, dy
            m_seg += 1
            dir_count[(ux, uy)] = dir_count.get((ux, uy), 0) + 1

    # subsets with no polygon objects:
    # total such subsets = 2^(m_point + m_seg)
    # degenerate among them:
    #  - all points only: 2^m_point
    #  - choose segments from at most one direction group, and any points
    #    => 2^m_point * (1 + sum_d (2^{c_d}-1))
    # subtract overlap of empty-segment case counted in both: 2^m_point
    # => degenerate_no_poly = 2^m_point * (sum_d 2^{c_d} - D + 1)
    # where D = number of direction groups
    # desired among no-poly subsets = total_no_poly - degenerate_no_poly
    # then any subset containing at least one polygon is always polygon in Minkowski sum
    # so final = (2^N -1) - degenerate_all
    # degenerate_all = degenerate_no_poly -1 (exclude empty subset)
    # final = 2^N - degenerate_no_poly

    pow2_point = pow(2, m_point, MOD)
    sum_pow_dir = 0
    for c in dir_count.values():
        sum_pow_dir = (sum_pow_dir + pow(2, c, MOD)) % MOD
    D = len(dir_count)

    deg_no_poly = pow2_point * ((sum_pow_dir - D + 1) % MOD) % MOD
    ans = (pow(2, N, MOD) - deg_no_poly) % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。