分数: 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