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$ 取模。
说明/提示
### 限制条件
- $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 翻译