B - よんてん
解説
/
入力は以下の形式で標準入力から与えられる。
与えられる点が 4 点の入力(N = 4)に正解すると、100 点満点に対して部分点として 4 点が与えられる。
与えられる点の数が 100 以下の入力(N \leq 100)に正解すると、100 点満点に対して部分点として、さらに 16 点が与えられる。
与えられる点の数が 1000 以下の入力(N \leq 1000)に正解すると、100 点満点に対して部分点として、さらに 30 点が与えられる。
いずれの 3 点も一直線上に並ばない 4 点の選び方の数を 1,000,000,007 で割った余りを 1 行で出力せよ。
なお、行の終端には改行が必要である。
実行時間制限: 2 sec / メモリ制限: 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
部分点
与えられる点の数が 100 以下の入力(N \leq 100)に正解すると、100 点満点に対して部分点として、さらに 16 点が与えられる。
与えられる点の数が 1000 以下の入力(N \leq 1000)に正解すると、100 点満点に対して部分点として、さらに 30 点が与えられる。
出力
なお、行の終端には改行が必要である。
入力例 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 通りである。