E - 凸図形の合成 / Composition of Convex Shapes Editorial by admin
Gemini 3.0 Flash (Thinking)概要
\(N\) 個の凸図形（点、線分、凸多角形）の中から 1 個以上を選び、そのミンコフスキー和が「面積を持つ凸多角形」になる組み合わせの数を求める問題です。
ミンコフスキー和の性質を利用すると、面積が \(0\) になる（＝点または線分になる）条件を特定できるため、全体からその条件に当てはまるものを引く「余事象」の考え方で解くことができます。
考察
1. ミンコフスキー和の性質と面積
凸図形 \(A, B\) のミンコフスキー和 \(A \oplus B\) は再び凸図形になります。この和の面積が \(0\) になる（凸多角形にならない）のは、以下のいずれかの場合に限られます。
- ケースA：選んだ図形がすべて「点」である。
- 点同士の和は点になります。
- ケースB：選んだ図形が「点」または「特定の同じ方向を向いた線分」のみで構成されている。
- 平行な線分同士の和は、やはり同じ傾きを持つ（より長い）線分になります。これに点を足しても位置がずれるだけで、形は線分のままです。
逆に、以下のいずれか一条件でも満たせば、ミンコフスキー和は必ず正の面積を持つ「凸多角形」になります。 - 少なくとも 1 つの「凸多角形（面積が正の図形）」を選んでいる。 - 異なる方向（傾き）を持つ 2 つ以上の「線分」を選んでいる。
2. 余事象によるカウント
「面積が正になる組み合わせ」を直接数えるのは難しいため、以下の手順で計算します。 1. 全組み合わせ: 空でない部分集合の総数 \(2^N - 1\) を求める。 2. 面積が 0 になる組み合わせ: 上記のケースAとケースBを数えて引く。
3. 図形の分類
与えられた各図形 \(P_i\) を以下の 3 種類に分類します。 - 多角形: 面積が正の図形。これを含めば即座に面積が正になります。 - 点: 向きを持たない図形。 - 線分: 特定の向き（傾き）を持つ図形。
ここで、入力で \(K_i \geq 3\) かつ頂点が同一直線上にある場合は「線分」として扱う必要がある点に注意してください。
アルゴリズム
図形の整理:
- \(N_{pts}\): 点の個数
- \(directions\): 各「方向（傾き）」ごとの線分の個数を管理するハッシュマップ
- 多角形については、個数だけ把握しておけば十分です（全組み合わせ \(2^N\) に含まれるため）。
方向の正規化:
- 線分の端点を \((x_1, y_1), (x_2, y_2)\) としたとき、ベクトル \((dx, dy) = (x_2-x_1, y_2-y_1)\) を求めます。
- \(g = \gcd(|dx|, |dy|)\) で割り、さらに「上半分（\(dx > 0\) または \(dx=0, dy>0\)）」の範囲に正規化することで、同じ傾きを同一視できるようにします。
計算式: 面積が \(0\) となる空でない部分集合の数は、包除原理の考え方を用いて以下のように表せます。
- 全ての「方向 \(d\)」について、(点と方向 \(d\) の線分のみからなる空でない部分集合) を足し合わせる。
- ただし、これでは「点のみからなる集合」を重複して数えてしまうため、調整が必要です。
数式にすると、面積が \(0\) の集合の個数は： $\(\left( \sum_{d \in \text{Directions}} (2^{N_{pts} + C_d} - 1) \right) - (M - 1)(2^{N_{pts}} - 1)\)\( ※ \)Cd\( は方向 \)d\( の線分の個数、\)M\( は異なる方向の総数です。 ※ 第 2 項は、「点のみの集合（\)2^{N{pts}}-1\( 通り）」が各方向 \)d\( の計算で \)M\( 回数えられているため、重複分の \)M-1$ 回を引いています。
- 最終回答:
$\(\text{Ans} = (2^N - 1) - \text{(面積 0 の個数)} \pmod{10^9+7}\)$
これを整理すると、コード内の式
pow2[N] - sum(2^{N_pts + C_d}) + (M - 1) * 2^{N_pts}が得られます。
計算量
- 時間計算量: \(O(\sum K_i + N \log (\max |X|))\)
- 各図形の頂点の走査に \(O(\sum K_i)\)。
- 線分の方向を求める際の最大公約数（GCD）計算に \(O(N \log (\max |X|))\)。
- ハッシュマップの操作は平均 \(O(N)\)。
- 空間計算量: \(O(\sum K_i)\)
- 頂点情報の保持および方向をカウントするマップに依存します。
実装のポイント
同一直線上の判定: \(K_i \geq 3\) のとき、最初の 3 点の外積が \(0\) かどうかで、多角形か線分かを判定できます。
巨大な座標: 座標が \(10^9\) と大きいため、傾きの管理には浮動小数点数（
double）を使わず、GCD で正規化した整数のペア(dx, dy)を辞書のキーにします。ゼロ除算の回避: \(dx=0\) の場合も GCD を使った正規化で自然に扱えます。
ソースコード
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()
この解説は gemini-3-flash-thinking によって生成されました。