F - 整数凸包

得分：$600$ 分

问题描述

在一个平面上有 $N$ 个点 $P_1, P_2, \dots, P_N$，点 $P_i$ 的坐标是 $(X_i, Y_i)$。已知没有三个点共线。

对于 $\{ P_1, P_2, \dots, P_N \}$ 的一个非空子集 $S$，我们定义 $S$ 的 凸包 如下：

• 凸包是包含 $S$ 所有点的最小凸多边形，使得多边形的边界上或内部的点都属于 $S$。

求满足凸包的面积为整数的子集 $S$ 的个数，对 $(10^9 + 7)$ 取模。

约束条件

• $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)$ 取模。

4
0 0
1 2
0 1
1 0

2

$ \{ P_1, P_2, P_4 \}$ 和 $\{ P_2, P_3, P_4 \}$ 满足条件。

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

4060436