概要

ミンコフスキー和が「凸多角形」にならないのは、実は 選んだ図形がすべて点・線分で、しかも線分がすべて同じ向きのときだけ です。
この性質を使って、条件を満たさない部分集合を数え上げ、全体 \(2^N-1\) から引くことで高速に解けます。

考察

まず、どんな部分集合 \(S\) のミンコフスキー和が凸多角形になるかを考えます。

1. 凸多角形を 1 つでも含めば必ず OK

ある部分集合に面積が正の凸多角形 \(Q\) が含まれているとします。
このとき、他の図形の和を \(R\) とすると

\[ Q \oplus R \]

になります。

\(R\) は空でないので、ある点 \(\mathbf{r} \in R\) が存在します。すると

\[ Q + \mathbf{r} \subseteq Q \oplus R \]

です。\(Q+\mathbf{r}\) は \(Q\) を平行移動したものなので、やはり面積は正です。
よって \(Q \oplus R\) も面積が正で、しかもミンコフスキー和は凸なので、結果は凸多角形です。

つまり、

• 1 個でも凸多角形が入っていれば、その部分集合は必ず有効

です。

---

2. 点と線分だけを選んだ場合

では、凸多角形を含まない場合を考えます。

点だけ

点のミンコフスキー和は点です。
したがって凸多角形にはなりません。

点 + 線分

点との和はただの平行移動です。
つまり点は「形の次元」を増やしません。

• 点 + 線分 = 線分
• 点 + 点 = 点

平行な線分どうし

同じ向きの線分どうしのミンコフスキー和は、やはり同じ直線方向の線分になります。
したがって、平行な線分だけをいくつ選んでも結果は線分のままです。

平行でない 2 本の線分がある

ここが重要です。
向きの異なる 2 本の線分を選ぶと、そのミンコフスキー和は平行四辺形になります。

例えばベクトル \(\mathbf{a}, \mathbf{b}\) に対して

\[ [0,\mathbf{a}] \oplus [0,\mathbf{b}] = \{ s\mathbf{a} + t\mathbf{b} \mid 0 \le s,t \le 1 \} \]

は、\(\mathbf{a}, \mathbf{b}\) が平行でなければ面積が正の平行四辺形です。
したがってこの時点で凸多角形確定です。

---

3. 「ダメな部分集合」の条件

以上より、ミンコフスキー和が凸多角形 にならない のは次の 2 種類だけです。

1. 点だけを選ぶ
2. 点を何個か選び、さらに線分を選ぶが、その線分がすべて同じ向き

これを数えれば、答えは

\[ (2^N - 1) - \text{ダメな部分集合数} \]

で求まります。

---

4. なぜ全探索できないか

部分集合は全部で \(2^N - 1\) 通りあり、\(N \le 5 \times 10^4\) なので全探索は不可能です。
そこで各図形を

• 点
• 線分（向きごとに分類）
• 凸多角形

にまとめ、個数だけで数え上げる のがポイントです。

---

5. 入力の図形の扱い

問題では \(K_i \ge 3\) でも、全頂点が一直線上ならその図形は「最短の線分」として扱います。
したがって各図形について必要なのは次の判定です。

• \(K_i=1\) : 点
• \(K_i=2\) : 線分
• \(K_i \ge 3\) :
  • 全頂点が一直線上 → 線分
  • そうでない → 凸多角形

一直線上かどうかは、最初の 2 点で作る方向ベクトルに対して、他の点との外積がすべて \(0\) かを見れば判定できます。

また、線分は「向き」でグループ化します。
例えば \((2,4)\) と \((-1,-2)\) は同じ向きの線分として同一視したいので、\(\gcd\) で約分し、符号をそろえて正規化します。

アルゴリズム

以下のように数えます。

1. 各図形を分類する

• 点の個数を \(P\) とする
• 線分は向きごとに個数 \(c_d\) を持つ連想配列で管理する
• 凸多角形は個数を数えなくてもよい（補集合で数えるため）

2. ダメな部分集合数を求める

点だけを選ぶ場合

空でない点の部分集合の数は

\[ 2^P - 1 \]

ある 1 つの向き \(d\) の線分だけを選ぶ場合

• その向きの線分から 1 本以上選ぶ方法：\(2^{c_d} - 1\)
• 点は自由に選べる：\(2^P\)

よって

\[ 2^P (2^{c_d} - 1) \]

通りです。

これをすべての向きについて足します。
異なる向きの線分を同時に選ぶと有効になってしまうため、ダメな場合は「向きが 1 種類」に限られ、各向きの数え上げは重複しません。

したがって、ダメな部分集合数は

\[ (2^P - 1) + 2^P \sum_d (2^{c_d} - 1) \]

です。

3. 全体から引く

全体の空でない部分集合数は

\[ 2^N - 1 \]

なので、答えは

\[ (2^N - 1) - \left[ (2^P - 1) + 2^P \sum_d (2^{c_d} - 1) \right] \]

を \(10^9+7\) で割った余りです。

計算量

• 時間計算量: \(O\!\left(\sum K_i + N\right)\)
• 空間計算量: \(O(N)\)

ここで \(\sum K_i \le 10^5\) なので十分高速です。

実装のポイント

• 線分の向きは、\((dx,dy)\) を \(\gcd(|dx|,|dy|)\) で割って正規化します。

  • さらに \((dx < 0)\) または \((dx = 0 \land dy < 0)\) のとき符号を反転し、逆向きも同じグループに入れます。

• \(K_i \ge 3\) で全頂点が一直線上のとき、問題文の条件より頂点は端から端へ順に並んでいるので、線分の向きは「最初の点」と「最後の点」で求めればよいです。

• 答えは補集合で計算するので、凸多角形は「存在する」ことだけが重要で、個別に何か処理する必要はありません。

• 個数計算のために \(2^0,2^1,\dots,2^N\) を前計算しておくと簡潔です。

  ソースコード

import sys
from math import gcd

MOD = 10**9 + 7

def solve():
    data = sys.stdin.buffer.read()
    n_data = len(data)
    idx = 0

    def next_int():
        nonlocal idx
        while idx < n_data and data[idx] <= 32:
            idx += 1
        sign = 1
        if data[idx] == 45:
            sign = -1
            idx += 1
        num = 0
        while idx < n_data and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return sign * num

    def norm(dx, dy):
        g = gcd(abs(dx), abs(dy))
        dx //= g
        dy //= g
        if dx < 0 or (dx == 0 and dy < 0):
            dx = -dx
            dy = -dy
        return dx, dy

    N = next_int()

    point_count = 0
    seg_groups = {}

    for _ in range(N):
        K = next_int()
        x1 = next_int()
        y1 = next_int()

        if K == 1:
            point_count += 1
            continue

        x2 = next_int()
        y2 = next_int()

        if K == 2:
            d = norm(x2 - x1, y2 - y1)
            seg_groups[d] = seg_groups.get(d, 0) + 1
            continue

        base_dx = x2 - x1
        base_dy = y2 - y1
        collinear = True
        lastx, lasty = x2, y2

        for _ in range(K - 2):
            x = next_int()
            y = next_int()
            if collinear and base_dx * (y - y1) - base_dy * (x - x1) != 0:
                collinear = False
            lastx, lasty = x, y

        if collinear:
            d = norm(lastx - x1, lasty - y1)
            seg_groups[d] = seg_groups.get(d, 0) + 1
        else:
            pass

    pow2 = [1] * (N + 1)
    for i in range(1, N + 1):
        pow2[i] = (pow2[i - 1] << 1) % MOD

    invalid = (pow2[point_count] - 1) % MOD
    s = 0
    for cnt in seg_groups.values():
        s += pow2[cnt] - 1
    invalid = (invalid + pow2[point_count] * (s % MOD)) % MOD

    ans = (pow2[N] - 1 - invalid) % MOD
    print(ans)

if __name__ == "__main__":
    solve()

---

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