E - Composition of Convex Shapes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

この問題では、凸図形とは以下のいずれかを指します。

  • 点：平面上の 1 点からなる集合
  • 線分：平面上の異なる 2 点を結ぶ線分（両端点および内部の点すべてからなる集合）
  • 凸多角形：3 個以上の頂点からなり、すべての頂点が同一直線上にはない凸多角形（頂点・辺上・内部の点すべてからなる集合）。このとき面積は正です。

高橋君は N 個の凸図形を持っています。i 番目の凸図形 P_i は K_i 個の頂点で表され、以下の規則に従います。

  • K_i = 1 のとき、P_i は点 (x_{i,1}, y_{i,1}) です。
  • K_i = 2 のとき、P_i は 2 点 (x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}) を結ぶ線分です。
  • K_i \geq 3 のとき、K_i 個の頂点がすべて同一直線上にない場合、P_i はそれらを頂点とする凸多角形です。K_i 個の頂点がすべて同一直線上にある場合、P_i はそれらすべてを含む最短の線分（すなわち、全頂点の凸包）です。

2 つの凸図形 A, B のミンコフスキー和 A \oplus B は次のように定義されます。

A \oplus B = \{ \mathbf{a} + \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B \}

ここで \mathbf{a} + \mathbf{b} は座標ごとの和を表します。凸図形同士のミンコフスキー和は再び凸図形となることが知られています。

N 個の凸図形から 1 個以上を選ぶ方法を考えます。各凸図形は最大 1 回しか選べません。すなわち、空でない部分集合 S \subseteq \{P_1, P_2, \ldots, P_N\} を 1 つ選びます。S に含まれるすべての図形のミンコフスキー和を

\bigoplus_{P \in S} P

と書きます。S がちょうど 1 つの図形からなる場合、この値はその図形自身です。ミンコフスキー和は結合的かつ可換であるため、二項演算を適用する順序によらず結果は一意に定まります。

空でない部分集合 S の選び方は 2^N - 1 通りあります。このうち、\bigoplus_{P \in S} P が凸多角形（すなわち、点でも線分でもなく、面積が正の凸多角形）となるものの個数を 10^9 + 7 で割った余りを求めてください。

制約

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq K_i \leq 50
  • \sum_{i=1}^{N} K_i \leq 10^5
  • |x_{i,j}| \leq 10^9,\ |y_{i,j}| \leq 10^9
  • 各凸図形について、与えられる K_i 個の頂点はすべて相異なる
  • K_i \geq 3 かつすべての頂点が同一直線上にない場合、頂点は反時計回りの順に与えられ、巡回的に連続する 3 頂点が同一直線上にあることはない（すなわち内角が 0° や 180° の頂点は存在しない）
  • K_i \geq 3 かつすべての頂点が同一直線上にある場合、頂点は全頂点を含む線分の一方の端点から他方の端点へ向かって順に並んでいる（すなわち、最初の頂点と最後の頂点がこの線分の両端点である）
  • すべての入力値は整数である

入力

入力は以下の形式で与えられます。

N
K_1
x_{1,1} y_{1,1}
x_{1,2} y_{1,2}
\vdots
x_{1,K_1} y_{1,K_1}
K_2
x_{2,1} y_{2,1}
x_{2,2} y_{2,2}
\vdots
x_{2,K_2} y_{2,K_2}
\vdots
K_N
x_{N,1} y_{N,1}
x_{N,2} y_{N,2}
\vdots
x_{N,K_N} y_{N,K_N}
  • 1 行目には、凸図形の個数 N が与えられます。
  • 続いて N 個の凸図形の情報が順に与えられます。
  • 各凸図形について、最初の 1 行に頂点数 K_i が与えられ、続く K_i 行のそれぞれに j 番目の頂点の x 座標 x_{i,j} と y 座標 y_{i,j} が空白区切りで与えられます。

出力

条件を満たす部分集合の個数を 10^9 + 7 で割った余りを 1 行に出力してください。

入力例 1

3
1
0 0
2
1 0
1 2
3
0 0
2 0
0 2

出力例 1

4

入力例 2

3
1
2 3
3
0 0
2 0
5 0
2
-1 0
4 0

出力例 2

0

入力例 3

6
1
1 -1
2
0 0
2 1
3
-2 -1
0 -1
3 -1
4
-1 0
2 0
2 2
-1 2
5
0 0
2 -1
4 0
3 2
1 2
2
-3 1
-1 4

出力例 3

56

入力例 4

10
1
0 0
1
5 -3
2
0 0
2 0
4
-3 -3
-1 -1
1 1
4 4
3
0 0
3 0
1 2
4
-2 1
2 1
2 4
-2 4
5
-3 0
-1 -2
2 -1
3 2
0 3
3
-5 -1
-3 -4
-1 -2
3
7 -1
7 0
7 3
6
0 0
2 -1
4 0
5 2
3 4
1 3

出力例 4

1008

入力例 5

1
50
0 1
1 3
2 5
3 7
4 9
5 11
6 13
7 15
8 17
9 19
10 21
11 23
12 25
13 27
14 29
15 31
16 33
17 35
18 37
19 39
20 41
21 43
22 45
23 47
24 49
25 51
26 53
27 55
28 57
29 59
30 61
31 63
32 65
33 67
34 69
35 71
36 73
37 75
38 77
39 79
40 81
41 83
42 85
43 87
44 89
45 91
46 93
47 95
48 97
49 99

出力例 5

0

Score : 466 pts

Problem Statement

In this problem, a convex figure refers to one of the following:

  • Point: A set consisting of a single point on the plane.
  • Line segment: A line segment connecting two distinct points on the plane (the set consisting of both endpoints and all interior points).
  • Convex polygon: A convex polygon with 3 or more vertices where not all vertices are collinear (the set consisting of all vertices, points on edges, and interior points). In this case, the area is positive.

Takahashi has N convex figures. The i-th convex figure P_i is represented by K_i vertices, following these rules:

  • If K_i = 1, then P_i is the point (x_{i,1}, y_{i,1}).
  • If K_i = 2, then P_i is the line segment connecting the two points (x_{i,1}, y_{i,1}) and (x_{i,2}, y_{i,2}).
  • If K_i \geq 3 and not all K_i vertices are collinear, then P_i is the convex polygon with those vertices. If K_i \geq 3 and all K_i vertices are collinear, then P_i is the shortest line segment containing all of them (i.e., the convex hull of all vertices).

The Minkowski sum A \oplus B of two convex figures A, B is defined as follows:

A \oplus B = \{ \mathbf{a} + \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B \}

Here, \mathbf{a} + \mathbf{b} denotes the coordinate-wise sum. It is known that the Minkowski sum of two convex figures is again a convex figure.

Consider ways to select one or more of the N convex figures. Each convex figure can be selected at most once. That is, we choose a non-empty subset S \subseteq \{P_1, P_2, \ldots, P_N\}. We write the Minkowski sum of all figures in S as

\bigoplus_{P \in S} P

If S consists of exactly one figure, this value is that figure itself. Since the Minkowski sum is associative and commutative, the result is uniquely determined regardless of the order in which the binary operation is applied.

There are 2^N - 1 ways to choose a non-empty subset S. Among these, find the number of subsets for which \bigoplus_{P \in S} P is a convex polygon (i.e., not a point or a line segment, but a convex polygon with positive area), modulo 10^9 + 7.

Constraints

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq K_i \leq 50
  • \sum_{i=1}^{N} K_i \leq 10^5
  • |x_{i,j}| \leq 10^9,\ |y_{i,j}| \leq 10^9
  • For each convex figure, the given K_i vertices are all distinct.
  • If K_i \geq 3 and not all vertices are collinear, the vertices are given in counterclockwise order, and no three cyclically consecutive vertices are collinear (i.e., there are no vertices with interior angle 0° or 180°).
  • If K_i \geq 3 and all vertices are collinear, the vertices are ordered from one endpoint of the line segment containing all vertices to the other endpoint (i.e., the first and last vertices are the two endpoints of this line segment).
  • All input values are integers.

Input

The input is given in the following format:

N
K_1
x_{1,1} y_{1,1}
x_{1,2} y_{1,2}
\vdots
x_{1,K_1} y_{1,K_1}
K_2
x_{2,1} y_{2,1}
x_{2,2} y_{2,2}
\vdots
x_{2,K_2} y_{2,K_2}
\vdots
K_N
x_{N,1} y_{N,1}
x_{N,2} y_{N,2}
\vdots
x_{N,K_N} y_{N,K_N}
  • The first line gives the number of convex figures N.
  • Then the information for N convex figures is given in order.
  • For each convex figure, the first line gives the number of vertices K_i, followed by K_i lines each containing the x-coordinate x_{i,j} and y-coordinate y_{i,j} of the j-th vertex, separated by a space.

Output

Print the number of subsets satisfying the condition, modulo 10^9 + 7, on a single line.

Sample Input 1

3
1
0 0
2
1 0
1 2
3
0 0
2 0
0 2

Sample Output 1

4

Sample Input 2

3
1
2 3
3
0 0
2 0
5 0
2
-1 0
4 0

Sample Output 2

0

Sample Input 3

6
1
1 -1
2
0 0
2 1
3
-2 -1
0 -1
3 -1
4
-1 0
2 0
2 2
-1 2
5
0 0
2 -1
4 0
3 2
1 2
2
-3 1
-1 4

Sample Output 3

56

Sample Input 4

10
1
0 0
1
5 -3
2
0 0
2 0
4
-3 -3
-1 -1
1 1
4 4
3
0 0
3 0
1 2
4
-2 1
2 1
2 4
-2 4
5
-3 0
-1 -2
2 -1
3 2
0 3
3
-5 -1
-3 -4
-1 -2
3
7 -1
7 0
7 3
6
0 0
2 -1
4 0
5 2
3 4
1 3

Sample Output 4

1008

Sample Input 5

1
50
0 1
1 3
2 5
3 7
4 9
5 11
6 13
7 15
8 17
9 19
10 21
11 23
12 25
13 27
14 29
15 31
16 33
17 35
18 37
19 39
20 41
21 43
22 45
23 47
24 49
25 51
26 53
27 55
28 57
29 59
30 61
31 63
32 65
33 67
34 69
35 71
36 73
37 75
38 77
39 79
40 81
41 83
42 85
43 87
44 89
45 91
46 93
47 95
48 97
49 99

Sample Output 5

0