頂点 \((0,0),(X_1,Y_1),(X_2,Y_2)\) を持つ三角形の面積は \(\displaystyle \frac{|X_1Y_2-X_2Y_1|}2\) です。したがって、この面積が整数となる条件は \(X_1Y_2-X_2Y_1\) が偶数となることです。つまり、面積が整数であることは \(X_1,Y_1,X_2,Y_2\) の偶奇にのみ依存します。

選んだ \(3\) 点が \(i,j,k\) 番目の点 \((i < j < k)\) とし、\(k\) を固定して考えます。面積は並行移動しても変わらないので、適切に並行移動し \((X_k,Y_k)=(0,0)\) とします。

まず選んだ \(3\) 点を頂点とする三角形の面積が整数であるような \(3\) つ組の個数を求め、そこから \(3\) 点が一直線上に並んでいるようなペアの個数を引くことで答えを求めていきます。

選んだ \(3\) 点を頂点とする三角形の面積が整数であるような \(3\) つ組の個数は \(X_i,Y_i\) の偶奇をまとめて計算することで高速に計算できます。

\(3\) 点が一直線上に並んでいるようなペアは \((0,0),(X_i,Y_i)\) を通る直線の傾きを計算し、まとめて計算することができます。

以上を各 \(k\) に対して計算することで答えを求めることができます。

実装例(Python3)

import sys
from collections import defaultdict
from math import gcd

input = sys.stdin.readline
n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append((x, y))
ans = 0
for i, (xi, yi) in enumerate(points):
    cnt = [0] * 4
    lines = defaultdict(int)
    for xj, yj in points[:i]:
        x, y = xj - xi, yj - yi
        cnt[2 * (x % 2) + y % 2] += 1
        g = gcd(x, y)
        x, y = x // g, y // g
        if x < 0 or (x == 0 and y < 0):
            x, y = -x, -y
        lines[x, y] += 1
    ans += i * (i - 1) // 2
    ans -= cnt[1] * cnt[2] + cnt[1] * cnt[3] + cnt[2] * cnt[3]
    ans -= sum(c * (c - 1) // 2 for c in lines.values())
print(ans)