#P17793. Making Shapes
Making Shapes
题目描述
给定 个两两不共线的二维向量。你可以用以下方式在二维平面上用这些向量构造图形:
- 从原点 开始。
- 选择一个向量,将该向量的线段加到当前点。例如,如果当前点在 ,你选择向量 ,则从当前点画一条线段到 ,并将当前点更新为 。
- 重复第 2 步,直到你再次回到原点。
每个向量可以重复使用任意多次。
请计算可以用上述步骤构造出的不同的、非退化(面积大于 )且凸的图形的数量,要求这些图形的构成向量按逆时针顺序排列,并且该图形可以通过平移被包含在一个 的正方形内。由于答案可能很大,请对 取模。
如果存在某种平行移动能使第一个图形与第二个图形重合,则认为这两个图形是相同的。
如果存在某种平行移动,使得图形内或边界上的每个点 都满足 ,则认为该图形可以被包含在 的正方形内。
输入格式
第一行包含两个整数 和 ,分别表示向量的数量和正方形的边长(,)。
接下来的 行,每行包含两个整数 和 ,表示第 个向量的 坐标和 坐标(,)。
保证任意两个向量都不平行,即对于任意 ,不存在实数 使得 且 。
输出格式
输出一个整数,表示满足条件的图形数量,对 取模。
输入输出样例 #1
输入 #1
3 3
-1 0
1 1
0 -1
输出 #1
3
输入输出样例 #2
输入 #2
3 3
-1 0
2 2
0 -1
输出 #2
1
输入输出样例 #3
输入 #3
3 1776966
-1 0
3 3
0 -2
输出 #3
296161
输入输出样例 #4
输入 #4
4 15
-4 -4
-1 1
-1 -4
4 3
输出 #4
1
输入输出样例 #5
输入 #5
5 10
3 -4
4 -3
1 -3
2 -3
-3 -4
输出 #5
0
输入输出样例 #6
输入 #6
5 1000000000
-2 4
2 -3
0 -4
2 4
-1 -3
输出 #6
9248783
说明/提示
第一个样例的所有图形如下:

第二个样例的唯一图形如下:

第四个样例的唯一图形如下:
