← 返回题目列表

AtCoder · abc202_f

F. 整数凸包

中文机器翻译题面 查看原题

分数: 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