← 返回题目列表

AtCoder · awc0079_e

E. 凸形状的构成

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

在这个问题中, 凸图 指以下其中一项:

  • 点:由平面上的单个点组成的集合。
  • 线段:连接平面上两个不同点的线段(由两个端点和所有内部点组成的集合)。
  • 凸多边形:具有 3 个或更多顶点的凸多边形,其中并非所有顶点都共线(由所有顶点、边上的点和内部点组成的集合)。在这种情况下,面积为正。

高桥有 N 凸数字。的 i第一个凸图 P_i 表示为 K_i 顶点,遵循以下规则:

  • If K_i = 1,那么 P_i 是重点 (x_{i,1}, y_{i,1}).
  • If K_i = 2,那么 P_i 是连接两点的线段 (x_{i,1}, y_{i,1}) 和 (x_{i,2}, y_{i,2}).
  • If K_i \geq 3 并非全部 K_i 顶点共线,则 P_i 是具有这些顶点的凸多边形。如果 K_i \geq 3 和所有 K_i 顶点共线,则 P_i 是包含所有这些的最短线段(即所有顶点的凸包)。

的 树的 闵可夫斯基总和 A \oplus B 两个凸图形 A, B 定义如下:

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

在这里, \mathbf{a} + \mathbf{b} 表示坐标总和。众所周知,两个凸图的闵可夫斯基和又是一个凸图。

考虑选择一个或多个的方法 N 凸数字。每个凸图形最多只能被选择一次。也就是说,我们选择一个非空子集 S \subseteq \{P_1, P_2, \ldots, P_N\}。我们将所有数字的闵可夫斯基和写为 S as

\bigoplus_{P \in S} P

If S 仅由一个数字组成,该值就是该数字本身。由于闵可夫斯基和是结合律和交换律的,因此无论二元运算的应用顺序如何,结果都是唯一确定的。

有 2^N - 1 选择非空子集的方法 S。其中,找出子集的数量 \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 顶点都是不同的。
  • If K_i \geq 3 并且并非所有顶点都共线,顶点按逆时针顺序给出,并且没有三个循环连续的顶点共线(即不存在具有内角的顶点) 0° or 180°).
  • If 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}
  • 第一行给出凸图形的数量 N.
  • 那么信息为 N 凸图按顺序给出。
  • 对于每个凸图形,第一行给出顶点数 K_i,然后是 K_i 行各包含 x- 坐标 x_{i,j} 和 y- 坐标 y_{i,j} 的 j- 第一个顶点,以空格分隔。

输出

打印满足条件的子集数量,模 10^9 + 7,在一行上。


示例输入 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