AT_abc202_f [ABC202F] Integer Convex Hull

题目描述

平面上有 $N$ 个点 $P_1, P_2, \dots, P_N$，其中 $P_i$ 的坐标为 $(X_i, Y_i)$。已知任意 $3$ 个点都不共线。

对于元素个数不少于 $3$ 的 $\{P_1, P_2, \dots, P_N\}$ 的任意子集 $S$，定义 $S$ 的凸包如下：

• 包含 $S$ 中所有点（在边界上或内部）的所有凸多边形中，面积最小的那个。

请计算使得凸包面积为整数的 $S$ 的总数，并对 $10^9 + 7$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

输出答案。注意需要对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

4
0 0
1 2
0 1
1 0

输出 #1

2

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $3 \leq N \leq 80$
• $0 \leq |X_i|, |Y_i| \leq 10^4$
• 任意 $3$ 个点不共线。
• 所有输入均为整数。

样例解释 1

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

由 ChatGPT 4.1 翻译