← 返回题目列表

AtCoder · tenka1_2012_final_b

B. 永天

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

問題文

x 坐标和 y 平面上坐标均为整数的点是 给出了 N 。

从这几点来看, 3 这些点也不排成一条直线。 4 有多少种选择点的方法? 使用除以1,000,000,007 后的余数来回答。


入力

输入是按以下格式从标准输入给出的。
N
x_1 y_1
:
x_N y_N
  • 1 线代表给定的点数。 N 。
  • 2 来自行 N 行包含i 第一点 x 座標 x_i 和 y 座標 y_i 用空格分隔。
  • 4 \leq N \leq 10^4
  • 0 \leq x_i \leq 99\ (1 \leq i \leq N)
  • 0 \leq y_i \leq 99\ (1 \leq i \leq N)
  • i \neq j 然后, x_i \neq x_j 或 y_i \neq y_j

部分点

给出的点是 4 点输入(N = 4)是正确的。100 部分积分换满分 4 点。 如果您对除上述数据集之外的所有满足
给出的点数是 100 输入以下内容(N \leq 100)是正确的。100 部分分数换成满分,以及 16 点。 如果您对除上述数据集之外的所有满足
给出的点数是 1000 输入以下内容(N \leq 1000)是正确的。100 部分分数换成满分,以及 30 点。 如果您对除上述数据集之外的所有满足

出力

哪个 3 这些点也不排成一条直线。 4 选择点的方式数量 除以 1,000,000,007 后的余数 1 行。
请注意,行尾需要换行。

入力例 1

4
0 0
0 1
1 0
1 1

出力例 1

1

入力例 2

5
0 0
0 1
0 2
2 0
2 2

出力例 2

3
  • \{(0,0),\ (0,1),\ (2,0),\ (2.2)\}, \{(0,0),\ (0,2),\ (2,0),\ (2.2)\}, \{(0,1),\ (0,2),\ (2,0),\ (2.2)\} 的 3 没错。