概要

\(N\) 個の点から3点を選び、面積が正の整数となる三角形を作る選び方の数を求める問題。面積の整数条件を「外積の偶奇」に帰着させ、座標のパリティ（偶奇）による分類と共線点の除外で高速に求める。

考察

面積の公式と整数条件

3点 \((x_i, y_i), (x_j, y_j), (x_k, y_k)\) を頂点とする三角形の面積は：

\[S = \frac{1}{2}|(x_j - x_i)(y_k - y_i) - (x_k - x_i)(y_j - y_i)|\]

ここで外積部分を \(C = (x_j - x_i)(y_k - y_i) - (x_k - x_i)(y_j - y_i)\) とおくと、条件は：

1. 面積が正: \(C \neq 0\)（3点が一直線上にない）
2. 面積が整数: \(C\) が偶数（\(|C|/2\) が整数になる）

つまり求めるのは 「\(C\) が偶数かつ \(C \neq 0\)」 である三つ組の個数です。

素朴なアプローチの問題点

全ての3点の組を調べると \(O(N^3)\) で、\(N = 3000\) では \(N^3 \approx 2.7 \times 10^{10}\) となりTLEします。

解決の鍵：偶奇による分類

\(C\) の偶奇は、各座標の \(\mod 2\) だけで決まります。つまり：

\[(x_j \oplus x_i) \land (y_k \oplus y_i) \oplus (x_k \oplus x_i) \land (y_j \oplus y_i) \equiv C \pmod{2}\]

（\(\oplus\) はXOR、\(\land\) はAND）

各点を \((x \bmod 2, y \bmod 2)\) で4種類に分類すれば、型の組み合わせ（高々 \(\binom{4+2}{3} = 20\) 通り）ごとに、外積が偶数かどうかを判定し、該当する三つ組の数を組合せ計算で求められます。

アルゴリズム

ステップ1: 外積が偶数の三つ組を数える

1. 各点を型 \((x \bmod 2, y \bmod 2)\) で4種類に分類し、各型の個数 \(cnt[0], cnt[1], cnt[2], cnt[3]\) を求める。
2. 全ての型の組み合わせ \((t_a, t_b, t_c)\)（\(t_a \leq t_b \leq t_c\)）について、外積のパリティが0かどうかを判定。
3. 0ならば、対応する点の個数から三つ組の数を計算して加算。
   • 3つ同じ型: \(\binom{cnt[t]}{3}\)
   • 2つ同じ型: \(\binom{cnt[t_a]}{2} \times cnt[t_c]\) など
   • 3つ異なる型: \(cnt[t_a] \times cnt[t_b] \times cnt[t_c]\)

ステップ2: 共線な三つ組を数える（引く分）

外積が0（共線）の三つ組も「外積が偶数」に含まれてしまうため、これを引きます。

• 各点 \(i\) について、他の全ての点 \(j\) への方向ベクトル \((dx, dy)\) をGCDで正規化して辞書で管理。
• 同じ方向のペア数 \(\binom{v}{2}\)（\(v\) は同一方向の点の個数）が、点 \(i\) を含む共線三つ組の数。
• 全ての \(i\) について合計すれば、各共線三つ組がちょうど1回数えられる（固定する点を最小インデックスにしているため）。

最終結果: \(\text{even\_count} - \text{collinear}\)

計算量

• 時間計算量: \(O(N^2)\)（ステップ2の共線判定が支配的）
• 空間計算量: \(O(N)\)（各点ごとの方向ベクトル辞書）

実装のポイント

• 方向ベクトルの正規化: \((dx, dy)\) をGCDで割り、さらに符号を統一する（\(dx < 0\) なら反転、\(dx = 0\) なら \(dy > 0\) に統一）。これにより同一直線上の点が同じキーにまとまる。

• 型の分類: (x % 2) * 2 + (y % 2) で0〜3に割り当て。Pythonの % は負の数でも非負の結果を返すため安全。

• 外積パリティの判定: ビット演算（XOR, AND）で簡潔に記述できる。

• i < j の制約: 共線三つ組のカウントで、各点 \(i\) からはインデックスが大きい点 \(j\) のみ見ることで、三つ組の重複カウントを防いでいる。

  ソースコード

import sys
from itertools import combinations

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    points = []
    for i in range(N):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        points.append((x, y))
    
    # Triangle area = |cross product| / 2
    # For area to be a positive integer, we need:
    # 1. cross product != 0 (not collinear)
    # 2. cross product is even (so area = |cross|/2 is integer)
    
    # cross product for points i,j,k:
    # (xj-xi)*(yk-yi) - (xk-xi)*(yj-yi)
    # This equals: xj*yk - xj*yi - xi*yk - xk*yj + xk*yi + xi*yj
    
    # Parity of cross product:
    # (xj-xi)*(yk-yi) - (xk-xi)*(yj-yi) mod 2
    # = (xj+xi)*(yk+yi) + (xk+xi)*(yj+yi) mod 2 (since -1 ≡ 1 mod 2)
    # Actually, let's think in terms of parities of coordinates.
    
    # Let px_i = X_i mod 2, py_i = Y_i mod 2
    # Cross product mod 2:
    # (xj-xi)(yk-yi) - (xk-xi)(yj-yi) mod 2
    # = (xj^xi)(yk^yi) ^ (xk^xi)(yj^yi)  (where ^ is XOR, multiplication is AND)
    # This is 0 when cross product is even.
    
    # We want: cross product is even AND cross product != 0
    # Count of "cross even" - count of "cross == 0 (collinear)"
    # But also total valid = (cross even and nonzero)
    
    # Approach: 
    # 1. Count triples with even cross product
    # 2. Subtract collinear triples (cross = 0)
    
    # For step 1: classify points by (x mod 2, y mod 2) into 4 categories
    # Cross product is even when (px_j^px_i)&(py_k^py_i) ^ (px_k^px_i)&(py_j^py_i) == 0
    
    # Let's enumerate: each point has type (a,b) where a=x%2, b=y%2
    # Types: (0,0), (0,1), (1,0), (1,1) — call them 0,1,2,3
    
    cnt = [0]*4
    for x, y in points:
        t = (x % 2) * 2 + (y % 2)
        cnt[t] += 1
    
    # For each triple of types, check if cross product is even
    types = [(0,0),(1,0),(0,1),(1,1)]
    
    def cross_parity(ta, tb, tc):
        ax, ay = types[ta]
        bx, by = types[tb]
        cx, cy = types[tc]
        return (((bx^ax)&(cy^ay)) ^ ((cx^ax)&(by^ay))) 
    
    even_count = 0
    # Count triples (with repetition of types allowed, but distinct points)
    for ta in range(4):
        for tb in range(ta, 4):
            for tc in range(tb, 4):
                if cross_parity(ta, tb, tc) != 0:
                    continue
                if ta == tb == tc:
                    c = cnt[ta] * (cnt[ta]-1) * (cnt[ta]-2) // 6
                elif ta == tb:
                    c = cnt[ta] * (cnt[ta]-1) // 2 * cnt[tc]
                elif tb == tc:
                    c = cnt[ta] * cnt[tb] * (cnt[tb]-1) // 2
                else:
                    c = cnt[ta] * cnt[tb] * cnt[tc]
                even_count += c
    
    # Step 2: count collinear triples using O(N^2) approach
    collinear = 0
    from math import gcd
    for i in range(N):
        slopes = {}
        for j in range(i+1, N):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            g = gcd(abs(dx), abs(dy))
            dx //= g
            dy //= g
            if dx < 0 or (dx == 0 and dy < 0):
                dx, dy = -dx, -dy
            slopes[(dx,dy)] = slopes.get((dx,dy), 0) + 1
        for v in slopes.values():
            collinear += v * (v-1) // 2
    
    print(even_count - collinear)

main()

---

この解説は claude4.6opus-thinking によって生成されました。