Overview

Rather than directly determining “which subsets have Minkowski sums that result in convex polygons with positive area,” we count the complement — the number of “subsets that only result in a point or a line segment” — and subtract from the total.
The key is classifying and counting the conditions under which the Minkowski sum remains degenerate (point/line segment) based on the type of each figure and the direction of line segments.

Analysis

First, each figure can be classified into one of three types:

1. Point
2. Line segment (\(K=2\), or \(K\ge3\) but all points are collinear)
3. True convex polygon (positive area)

Key Property 1: If even one true convex polygon is included, the result is a convex polygon

The Minkowski sum “never decreases in dimension,” so if at least one 2-dimensional figure (convex polygon with positive area) is included, the sum is also 2-dimensional.
Therefore, the result is degenerate (point/line segment) only when we select only points and line segments.

Key Property 2: Directions of line segments

• Adding only line segments with the same direction (parallel) → the result is a line segment in the same direction
• Adding two or more line segments with different directions → the result becomes 2-dimensional, forming a convex polygon

In other words, to keep the result degenerate within the world of only points and line segments: - Line segments can only be chosen from a single direction group (choosing 0 is also allowed) - Any number of points can be chosen (they only cause translation)

Why a naive approach doesn’t work

There are \(2^N-1\) subsets, and since \(N\le 5\times10^4\), exhaustive enumeration is impossible.
Instead, we reduce the problem to a combinatorial calculation using “counts per direction.”

---

Let \(m_{\text{point}}\) be the number of points, \(m_{\text{seg}}\) be the number of line segments, and
\(c_d\) be the number of line segments in direction group \(d\) (with \(D\) groups total).

The number of degenerate subsets (including the empty set) consisting only of points and line segments is:

• Choosing only points: \(2^{m_{\text{point}}}\)
• Choosing line segments from exactly one direction group:
  For each \(d\), there are \((2^{c_d}-1)\) ways (non-empty selection), multiplied by \(2^{m_{\text{point}}}\) for free choice of points

Therefore: [ \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) ]

The total number of subsets (including empty) is \(2^N\).
The “number of non-empty subsets whose Minkowski sum is a convex polygon” is simply: [ 2^N-\text{deg_no_poly} ] (This works because the empty set is included only on the degenerate side, so it cancels out exactly.)

Algorithm

1. Read all figures.
2. For each figure:
   • If \(K=1\), count it as a point.
   • Otherwise, check “whether all points are collinear” using cross products.
   • If not collinear, it’s a true convex polygon (its count is not directly used).
   • If collinear, treat it as a line segment and reduce the endpoint difference vector to obtain a direction key:
     • Divide \((dx,dy)\) by \(\gcd\)
     • Normalize the sign (negate if \(dx<0\), or if \(dx=0\) and \(dy<0\))
     • Handle vertical and horizontal cases similarly to ensure uniqueness
   • Increment the count for that direction group.
3. Compute the formula: [ \text{deg_no_poly} =2^{m_{\text{point}}}\left(\sum_d2^{c_d}-D+1\right)\pmod{M} ]
4. Output the answer: [ \text{ans}=2^N-\text{deg_no_poly}\pmod{M} ]

Complexity

• Time complexity: \(O\!\left(\sum K_i\right)\)
  (collinearity check performed once per figure)
• Space complexity: \(O(D)\)
  (hash map for direction groups)

Implementation Notes

• Collinearity is checked by taking two reference points \((x_0,y_0),(x_1,y_1)\) and verifying for each point whether the cross product [ (x_1-x_0)(y-y_0)-(y_1-y_0)(x-x_0) ] equals 0.

• When \(K\ge3\) and all points are collinear, by the problem’s guarantees, the endpoints can be taken as the first and last points.

• Without direction normalization, the same line direction could be treated as two different directions (e.g., \((1,2)\) and \((-1,-2)\)), leading to WA.

• At the end, always correct for negative values under \(\bmod (10^9+7)\) before outputting.

  Source Code

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()

---

This editorial was generated by gpt-5.3-codex.