B - 格子点と整数 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

諸君、私は整数が好きだ。
私は格子点が好きだ。
私は面積が好きだ。
私は三角形が好きだ。
私は座標平面上の、頂点が全て格子点上にある、面積が整数の三角形が大好きだ。
格子点の集合をみたとき、その中の任意の 3 点を選んで作ることができる面積が整数の三角形の個数を数えるときは心が踊る。
心が踊るが、格子点が多いと数えるのが面倒臭い。
ぜひ有能なプログラマーである諸君に私の代わりに数えてほしい。
N 個の格子点を与えるので、その中の任意の 3 点を選んで作ることができる、面積が整数の三角形の個数を数えるプログラムを作って欲しい。面積が 0 の三角形は三角形とは認めん！
ちなみに、格子点というのは座標平面上の点 (x,y) のうち x も y も整数である点のことである。

入力

入力は以下の形式で標準入力から与えられる。

 N  
 x_1   y_1 
 x_2   y_2 
:
 x_N   y_N
  • 1 行目には、格子点の個数を表す整数 N (3 ≦ N ≦ 100) が与えられる。
  • 2 行目から N 行では、2つの整数が空白区切りで与えられる。
    (x_i, y_i)　(1 ≦ x_i, y_i ≦ 10^9) は i 番目の格子点の位置である。同じ格子点が二度与えられることはない。( i \neq j ならば (x_i, y_i) \neq (x_j, y_j) )

出力

N 個の格子点のうち 3 つを選んで作ることができる面積が正の整数である三角形の個数を一行で出力せよ。
なお、出力の最後には改行を入れること。

入力例１

3
1 1
1 2
3 1

出力例１

1
(1,1), (1, 2), (3, 1) の面積が 1 の三角形が一つだけ作れる。

入力例2

3
1 1
1 2
2 1

出力例2

0
三角形 (1, 1) (1, 2) (2, 1) の面積は 0.5 で整数ではない。これ以外に三角形は作ることができない。

入力例3

3
1 1
2 2
3 3

出力例3

0
3 点は一直線上に並ぶので、三角形を作ることができない。

入力例4

8
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3

出力例4

38