Overview

The Minkowski sum fails to be a “convex polygon” only when all chosen figures are points or line segments, and moreover all line segments have the same direction.
Using this property, we can count the subsets that do not satisfy the condition and subtract them from the total \(2^N-1\) to solve the problem efficiently.

Analysis

First, let’s consider which subsets \(S\) have a Minkowski sum that forms a convex polygon.

1. Including even one convex polygon always works

Suppose a subset contains a convex polygon \(Q\) with positive area.
Let \(R\) be the Minkowski sum of the remaining figures, so the result is

\[ Q \oplus R \]

Since \(R\) is non-empty, there exists some point \(\mathbf{r} \in R\). Then

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

\(Q+\mathbf{r}\) is a translation of \(Q\), so it still has positive area.
Therefore \(Q \oplus R\) also has positive area, and since Minkowski sums preserve convexity, the result is a convex polygon.

In other words:

• If even one convex polygon is included, the subset is always valid

---

2. Selecting only points and line segments

Now consider the case where no convex polygon is included.

Points only

The Minkowski sum of points is a point.
Therefore it does not form a convex polygon.

Points + line segments

The sum with a point is just a translation.
That is, points do not increase the “dimension of the shape.”

• Point + line segment = line segment
• Point + point = point

Parallel line segments

The Minkowski sum of line segments with the same direction is again a line segment in the same direction.
Therefore, no matter how many parallel line segments you choose, the result remains a line segment.

Two non-parallel line segments exist

This is the key observation.
Choosing two line segments with different directions produces a parallelogram as their Minkowski sum.

For example, for vectors \(\mathbf{a}, \mathbf{b}\):

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

If \(\mathbf{a}, \mathbf{b}\) are not parallel, this is a parallelogram with positive area.
Therefore, at this point it is guaranteed to be a convex polygon.

---

3. Conditions for “bad subsets”

From the above, the Minkowski sum fails to be a convex polygon in exactly two cases:

1. Only points are selected
2. Some points are selected along with line segments, but all line segments have the same direction

By counting these, the answer is

\[ (2^N - 1) - \text{number of bad subsets} \]

---

4. Why brute force is impossible

There are \(2^N - 1\) total subsets, and since \(N \le 5 \times 10^4\), brute force is infeasible.
Instead, we classify each figure as:

• Point
• Line segment (grouped by direction)
• Convex polygon

and count using only the quantities of each type.

---

5. Handling input figures

Even if \(K_i \ge 3\), if all vertices are collinear, the figure is treated as a “line segment.”
Therefore, the necessary classification for each figure is:

• \(K_i=1\): point
• \(K_i=2\): line segment
• \(K_i \ge 3\):
  • All vertices are collinear → line segment
  • Otherwise → convex polygon

Collinearity can be checked by computing the direction vector from the first two points and verifying that the cross product with every other point is \(0\).

Also, line segments are grouped by “direction.”
For example, \((2,4)\) and \((-1,-2)\) should be treated as the same direction, so we normalize by dividing by \(\gcd\) and standardizing the sign.

Algorithm

We count as follows.

1. Classify each figure

• Let \(P\) be the number of points
• Manage line segments with an associative array holding counts \(c_d\) for each direction \(d\)
• Convex polygons don’t need individual counting (since we use the complement)

2. Compute the number of bad subsets

Selecting only points

The number of non-empty subsets of points is

\[ 2^P - 1 \]

Selecting line segments of only one direction \(d\)

• Ways to choose at least one line segment of that direction: \(2^{c_d} - 1\)
• Points can be freely chosen: \(2^P\)

So there are

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

such subsets.

Sum this over all directions.
Since choosing line segments of different directions simultaneously makes the subset valid, bad cases are restricted to “exactly one direction,” and the counts for each direction do not overlap.

Therefore, the number of bad subsets is

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

3. Subtract from the total

The total number of non-empty subsets is

\[ 2^N - 1 \]

So the answer is

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

taken modulo \(10^9+7\).

Complexity

• Time complexity: \(O\!\left(\sum K_i + N\right)\)
• Space complexity: \(O(N)\)

Since \(\sum K_i \le 10^5\), this is sufficiently fast.

Implementation Notes

• The direction of a line segment is normalized by dividing \((dx,dy)\) by \(\gcd(|dx|,|dy|)\).

  • Additionally, if \((dx < 0)\) or \((dx = 0 \land dy < 0)\), flip the sign so that opposite directions are grouped together.

• When \(K_i \ge 3\) and all vertices are collinear, by the problem’s conditions the vertices are listed in order from one end to the other, so the direction can be determined from the “first point” and the “last point.”

• Since the answer is computed via the complement, for convex polygons only their “existence” matters — no individual processing is needed.

• Precomputing \(2^0, 2^1, \dots, 2^N\) makes the counting concise.

  Source Code

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

---

This editorial was generated by gpt-5.4-high.