Overview

Given \(N\) convex shapes (points, line segments, convex polygons), we need to find the number of ways to select 1 or more of them such that their Minkowski sum becomes a “convex polygon with positive area.”

By leveraging the properties of Minkowski sums, we can identify the conditions under which the area becomes \(0\) (i.e., the result is a point or a line segment). This allows us to solve the problem using the “complementary counting” approach — subtracting the invalid combinations from the total.

Analysis

1. Properties of Minkowski Sums and Area

The Minkowski sum \(A \oplus B\) of convex shapes \(A, B\) is again a convex shape. The area of this sum becomes \(0\) (i.e., does not form a convex polygon) only in the following cases:

• Case A: All selected shapes are “points.”
  • The sum of points is a point.
• Case B: The selected shapes consist only of “points” and “line segments all pointing in the same direction.”
  • The sum of parallel line segments results in a (longer) line segment with the same slope. Adding points to this only shifts the position without changing the shape from a line segment.

Conversely, if at least one of the following conditions is met, the Minkowski sum is guaranteed to be a “convex polygon” with positive area: - At least one “convex polygon (a shape with positive area)” is selected. - Two or more “line segments” with different directions (slopes) are selected.

2. Counting via Complementary Approach

Since directly counting “combinations with positive area” is difficult, we compute as follows: 1. Total combinations: Find the total number of non-empty subsets \(2^N - 1\). 2. Combinations with area 0: Count the cases from Case A and Case B above, and subtract them.

3. Classification of Shapes

Each given shape \(P_i\) is classified into one of the following 3 types: - Polygon: A shape with positive area. Including one immediately guarantees positive area. - Point: A shape with no direction. - Line segment: A shape with a specific direction (slope).

Note that when \(K_i \geq 3\) but all vertices are collinear, the shape must be treated as a “line segment.”

Algorithm

1. Organizing the shapes:

   • \(N_{pts}\): Number of points
   • \(directions\): A hash map managing the number of line segments for each “direction (slope)”
   • For polygons, it suffices to just track their count (since they are included in the total \(2^N\) combinations).

2. Direction normalization:

   • Given the endpoints of a line segment \((x_1, y_1), (x_2, y_2)\), compute the vector \((dx, dy) = (x_2-x_1, y_2-y_1)\).
   • Divide by \(g = \gcd(|dx|, |dy|)\), then further normalize to the “upper half (\(dx > 0\), or \(dx=0, dy>0\))” range, so that line segments with the same slope are identified as equivalent.

3. Formula: The number of non-empty subsets with area \(0\) can be expressed using an inclusion-exclusion-like approach:

   • For each “direction \(d\)”, add up (the number of non-empty subsets consisting only of points and line segments with direction \(d\)).
   • However, this overcounts “subsets consisting only of points,” so an adjustment is needed.

Formally, the number of subsets with area \(0\) is: $\(\left( \sum_{d \in \text{Directions}} (2^{N_{pts} + C_d} - 1) \right) - (M - 1)(2^{N_{pts}} - 1)\)\( where \)Cd\( is the number of line segments with direction \)d\(, and \)M\( is the total number of distinct directions. The second term accounts for the fact that "point-only subsets (\)2^{N{pts}}-1\( possibilities)" are counted \)M\( times across each direction \)d\(, so we subtract the \)M-1$ redundant counts.

1. Final answer: $\(\text{Ans} = (2^N - 1) - \text{(number with area 0)} \pmod{10^9+7}\)$ Simplifying this yields the formula used in the code: pow2[N] - sum(2^{N_pts + C_d}) + (M - 1) * 2^{N_pts}.

Complexity

• Time complexity: \(O(\sum K_i + N \log (\max |X|))\)
  • Scanning the vertices of each shape takes \(O(\sum K_i)\).
  • GCD computation for determining line segment directions takes \(O(N \log (\max |X|))\).
  • Hash map operations take \(O(N)\) on average.
• Space complexity: \(O(\sum K_i)\)
  • Depends on storing vertex information and the direction counting map.

Implementation Notes

• Collinearity check: When \(K_i \geq 3\), you can determine whether the shape is a polygon or a line segment by checking whether the cross product of the first 3 points is \(0\).

• Large coordinates: Since coordinates can be as large as \(10^9\), do not use floating-point numbers (double) for managing slopes. Instead, use GCD-normalized integer pairs (dx, dy) as dictionary keys.

• Avoiding division by zero: The case \(dx=0\) is naturally handled by the GCD-based normalization.

  Source Code

import sys
import math

# Use a generator to read input values one by one to save memory
def get_input():
    for line in sys.stdin:
        for word in line.split():
            yield word

def get_direction(x1, y1, x2, y2):
    """
    Calculate the normalized direction vector of a line segment.
    The direction is represented by (dx, dy) where gcd(|dx|, |dy|) = 1
    and the vector is in the upper half-plane (dx > 0 or (dx == 0 and dy > 0)).
    """
    dx = x2 - x1
    dy = y2 - y1
    # Since vertices are distinct, dx and dy are not both zero.
    g = math.gcd(abs(dx), abs(dy))
    dx //= g
    dy //= g
    # Normalize the direction vector
    if dx < 0 or (dx == 0 and dy < 0):
        dx = -dx
        dy = -dy
    return (dx, dy)

def solve():
    input_gen = get_input()
    
    try:
        line = next(input_gen)
    except StopIteration:
        return
        
    N = int(line)
    
    N_pts = 0
    directions = {}
    
    for _ in range(N):
        try:
            K_str = next(input_gen)
        except StopIteration:
            break
        K = int(K_str)
        
        if K == 1:
            # The figure is a point
            next(input_gen) # x coordinate
            next(input_gen) # y coordinate
            N_pts += 1
        elif K == 2:
            # The figure is a line segment
            x1 = int(next(input_gen))
            y1 = int(next(input_gen))
            x2 = int(next(input_gen))
            y2 = int(next(input_gen))
            d = get_direction(x1, y1, x2, y2)
            directions[d] = directions.get(d, 0) + 1
        else:
            # K >= 3: The figure is either a convex polygon or a line segment
            x1 = int(next(input_gen))
            y1 = int(next(input_gen))
            x2 = int(next(input_gen))
            y2 = int(next(input_gen))
            x3 = int(next(input_gen))
            y3 = int(next(input_gen))
            
            # Check for collinearity using the cross product of (x2-x1, y2-y1) and (x3-x2, y3-y2).
            # If the cross product is zero, the first three points are collinear.
            # Due to the "no three consecutive vertices are collinear" rule for polygons,
            # this implies all vertices must be collinear if the first three are.
            is_collinear = (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2) == 0
            
            last_x, last_y = x3, y3
            for _ in range(3, K):
                last_x = int(next(input_gen))
                last_y = int(next(input_gen))
                
            if is_collinear:
                # All vertices are collinear, so it's a line segment.
                # The endpoints are the first and the last given vertices.
                d = get_direction(x1, y1, last_x, last_y)
                directions[d] = directions.get(d, 0) + 1
            else:
                # Not collinear, so it's a convex polygon (area > 0).
                pass

    MOD = 10**9 + 7
    
    # Precompute powers of 2 up to N modulo 10^9 + 7
    pow2 = [1] * (N + 1)
    for i in range(1, N + 1):
        pow2[i] = (pow2[i-1] * 2) % MOD
    
    # The Minkowski sum of a subset of convex shapes has area 0 if and only if 
    # all shapes in the subset are points or line segments that are parallel to each other.
    # Otherwise, the Minkowski sum is a convex polygon (area > 0).
    
    num_dirs = len(directions)
    
    # Total number of non-empty subsets is 2^N - 1.
    # We subtract the number of non-empty subsets that result in area 0.
    # Non-empty subsets with area 0 are:
    # 1. Non-empty subsets consisting only of points.
    # 2. For each direction d, subsets consisting of points and at least one line segment 
    #    of direction d.
    
    # Using inclusion-exclusion or partition logic:
    # Area-zero subsets (including empty) = sum_d 2^(N_pts + C_d) - (num_dirs - 1) * 2^N_pts
    # Number of area > 0 subsets = (2^N - 1) - (Area-zero subsets - 1)
    # Area > 0 subsets = 2^N - sum_d 2^(N_pts + C_d) + (num_dirs - 1) * 2^N_pts
    
    ans = pow2[N]
    
    sum_term = 0
    for d in directions:
        C_d = directions[d]
        sum_term = (sum_term + pow2[N_pts + C_d]) % MOD
        
    ans = (ans - sum_term) % MOD
    ans = (ans + (num_dirs - 1) * pow2[N_pts]) % MOD
    
    # Final answer modulo 10^9 + 7
    print(ans % MOD)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-thinking.