B - よんてん Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

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 通りである。