D - 整数面積の三角形 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

平面上に N 個の点があります。i 番目の点 (1 \leq i \leq N) は座標 (X_i, Y_i) に位置しています。

高橋君は、これらの N 個の点から異なる 3 個の点を選んで（選ぶ順序は区別しない）、それらを頂点とする三角形を作ることを考えています。3 個の点の選び方のうち、以下の条件をともに満たすものの個数を求めてください。

  • 選んだ 3 点は一直線上に並んでいない。すなわち、それらを頂点とする三角形の面積は正である。
  • 選んだ 3 点を頂点とする三角形の面積が整数である。

制約

  • 3 \leq N \leq 3000
  • -10^9 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • -10^9 \leq Y_i \leq 10^9 (1 \leq i \leq N)
  • i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j)（すべての点は互いに異なる）
  • 入力はすべて整数である

入力

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • 1 行目には、点の個数を表す整数 N が与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の点の x 座標を表す整数 X_i と y 座標を表す整数 Y_i が、スペース区切りで与えられる。

出力

上記の条件をともに満たす選び方の個数を、1 行で出力せよ。

入力例 1

5
0 0
2 0
0 2
1 0
0 1

出力例 1

5

入力例 2

5
-2 0
-1 0
0 0
1 0
2 0

出力例 2

0

入力例 3

12
0 0
2 0
0 2
2 2
1 1
3 1
1 3
3 3
-1 0
0 -1
4 2
2 4

出力例 3

149

入力例 4

30
-1000000000 -1000000000
1000000000 -1000000000
-1000000000 1000000000
1000000000 1000000000
0 0
1 0
0 1
1 1
2 3
3 2
-4 5
5 -4
10 10
20 20
30 30
-10 -10
7 14
14 7
-7 14
14 -7
123456789 987654321
987654321 123456789
-123456789 987654321
987654321 -123456789
500000000 0
0 500000000
-500000000 0
0 -500000000
333333333 -333333333
-333333333 333333333

出力例 4

2572

入力例 5

3
-1000000000 -1000000000
1000000000 -1000000000
-1000000000 999999999

出力例 5

1

Score : 400 pts

Problem Statement

There are N points on a plane. The i-th point (1 \leq i \leq N) is located at coordinates (X_i, Y_i).

Takahashi is thinking about choosing 3 distinct points from these N points (the order of selection does not matter) to form a triangle with those points as vertices. Find the number of ways to choose 3 points that satisfy both of the following conditions:

  • The chosen 3 points are not collinear. That is, the area of the triangle with those points as vertices is positive.
  • The area of the triangle with the chosen 3 points as vertices is an integer.

Constraints

  • 3 \leq N \leq 3000
  • -10^9 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • -10^9 \leq Y_i \leq 10^9 (1 \leq i \leq N)
  • If i \neq j, then (X_i, Y_i) \neq (X_j, Y_j) (all points are distinct)
  • All inputs are integers

Input

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • The first line contains an integer N representing the number of points.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains an integer X_i representing the x-coordinate and an integer Y_i representing the y-coordinate of the i-th point, separated by a space.

Output

Output the number of ways to choose points that satisfy both of the above conditions, in a single line.

Sample Input 1

5
0 0
2 0
0 2
1 0
0 1

Sample Output 1

5

Sample Input 2

5
-2 0
-1 0
0 0
1 0
2 0

Sample Output 2

0

Sample Input 3

12
0 0
2 0
0 2
2 2
1 1
3 1
1 3
3 3
-1 0
0 -1
4 2
2 4

Sample Output 3

149

Sample Input 4

30
-1000000000 -1000000000
1000000000 -1000000000
-1000000000 1000000000
1000000000 1000000000
0 0
1 0
0 1
1 1
2 3
3 2
-4 5
5 -4
10 10
20 20
30 30
-10 -10
7 14
14 7
-7 14
14 -7
123456789 987654321
987654321 123456789
-123456789 987654321
987654321 -123456789
500000000 0
0 500000000
-500000000 0
0 -500000000
333333333 -333333333
-333333333 333333333

Sample Output 4

2572

Sample Input 5

3
-1000000000 -1000000000
1000000000 -1000000000
-1000000000 999999999

Sample Output 5

1