Overview

Given \(N\) convex figures, we need to find the number of non-empty subsets whose Minkowski sum is a convex polygon with positive area. We solve this by counting the complement (cases where the area is not positive) and subtracting from the total.

Analysis

Minkowski Sum and Types of Figures

Let’s organize the properties of Minkowski sums.

• The Minkowski sum with a point is simply a translation, so adding any number of points does not change the “shape” of the figure.
• The Minkowski sum of line segments: if they have the same direction, the result is a longer line segment (remains 1-dimensional); if they have different directions, the result is a parallelogram (a convex polygon with positive area).
• If even one convex polygon (with positive area) is included, the Minkowski sum is always a convex polygon with positive area (the area never decreases).

Conditions for “Bad” Subsets Where Area Is Not Positive

The conditions under which the Minkowski sum does not become a convex polygon (i.e., remains only a point or line segment) are:

1. No convex polygon is selected (including even one convex polygon guarantees positive area)
2. All selected line segments have the same direction (if there are two or more line segments with different directions, a parallelogram is formed, resulting in positive area)

In other words, “bad” subsets are one of the following: - Subsets consisting only of points (\(2^{\text{num\_points}} - 1\) ways) - Subsets consisting only of points and line segments of a single direction (counted for each direction)

Counting via Complement

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

The number of bad subsets is:

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

where \(P\) is the number of points and \(c_d\) is the number of line segments with direction \(d\). The first term covers “points only,” and the second term covers “points (0 or more) + line segments of direction \(d\) (1 or more).”

Algorithm

1. Classify each convex figure as a point, line segment, or convex polygon.
   • All vertices are the same point → point
   • All vertices are collinear → line segment (normalize and record the direction)
   • Otherwise → convex polygon
2. Normalize the direction of line segments: divide the direction vector \((dx, dy)\) by \(\gcd\), and unify the sign (so that the first non-zero component is positive).
3. Aggregate the number of line segments for each direction.
4. Compute the answer using the complement formula.

Complexity

• Time complexity: \(O(\sum K_i + D)\) (\(D\) is the number of distinct directions, at most \(N\))
  • Classification of each figure takes \(O(K_i)\), aggregation and computation take \(O(N)\)
• Space complexity: \(O(\sum K_i + N)\)

Implementation Notes

• Collinearity check: Using the first two distinct points as a reference, check whether the cross product with all remaining points is 0.

• Direction normalization: Divide the direction vector \((dx, dy)\) by \(\gcd(|dx|, |dy|)\), and unify the sign so that “\(dx > 0\)” or “\(dx = 0\) and \(dy > 0\).” This allows line segments with the same line direction to be grouped together.

• When \(K_i \geq 3\) but all vertices are collinear, by the problem’s definition, it must be treated as a line segment. In the code, collinearity is checked after removing duplicate vertices.

• Use pow(2, n, MOD) for fast modular exponentiation.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.