分数: 600 点
问题陈述
我们有 N 点 P_1, P_2, \dots, P_N 在飞机上。的坐标 P_i is (X_i, Y_i)。我们知道没有三点在同一条线上。
对于子集 S of \{ P_1, P_2, \dots, P_N \} 至少有三个元素,让我们定义 凸包 of S 如下:
- 凸包是具有最小面积的凸多边形,使得每个点 S 位于该多边形的内部或圆周上。
求模数 (10^9 + 7),子集 S 使得凸包的面积为整数。
约束
- 3 \leq N \leq 80
- 0 \leq |X_i|, |Y_i| \leq 10^4
- 没有三个点位于同一条线上。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
打印答案。请注意,系统会要求您求模数 (10^9 + 7).
示例输入 1
4 0 0 1 2 0 1 1 0
示例输出 1
2
\{ P_1, P_2, P_4 \} 和 \{ P_2, P_3, P_4 \} 满足条件。
示例输入 2
23 -5255 7890 5823 7526 5485 -113 7302 5708 9149 2722 4904 -3918 8566 -3267 -3759 2474 -7286 -1043 -1230 1780 3377 -7044 -2596 -6003 5813 -9452 -9889 -7423 2377 1811 5351 4551 -1354 -9611 4244 1958 8864 -9889 507 -8923 6948 -5016 -6139 2769 4103 9241
示例输出 2
4060436