AT_abc202_f.[ABC202F] Integer Convex Hull

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

平面上有 $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
```
4
0 0
1 2
0 1
1 0
```
输出#1
```
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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页