概要

平面上の \(N\) 個の点から3点を選んで三角形を作るとき、「面積が正」かつ「面積が整数」であるような選び方の個数を求める問題です。

---

考察

1. 面積が整数になる条件

3つの頂点の座標を \((x_1, y_1), (x_2, y_2), (x_3, y_3)\) とすると、この3点がつくる三角形の面積 \(S\) は、以下の公式（外積）で求められます。 $\(S = \frac{1}{2} |(x_1 - x_3)(y_2 - y_3) - (x_2 - x_3)(y_1 - y_3)|\)$

面積 \(S\) が整数になるということは、「面積の2倍（ \(2S\) ）が偶数になる」ことと同値です。 $\(2S = |(x_1 - x_3)(y_2 - y_3) - (x_2 - x_3)(y_1 - y_3)| \equiv 0 \pmod 2\)$

この式の値の偶奇は、各座標の偶奇（パリティ）のみに依存します。 したがって、すべての点を \(x\) 座標と \(y\) 座標の偶奇に応じて、以下の4つのグループに分類できます。 - グループ0: (偶数, 偶数) - グループ1: (偶数, 奇数) - グループ2: (奇数, 偶数) - グループ3: (奇数, 奇数)

4つのグループから重複を許して3つのグループを選ぶ組み合わせは \(\binom{4+3-1}{3} = 20\) 通りしかありません。それぞれの組み合わせについて、代表値（例えば \((0,0), (0,1)\) など）を用いて \(2S \equiv 0 \pmod 2\) となるかを判定し、条件を満たす場合は各グループの要素数から3点の選び方の数を足し合わせることで、「面積の2倍が偶数になる3点の組」を \(O(N)\) で高速に数え上げることができます。

2. 面積が正（一直線上にない）になる条件

上記の方法で求めた「面積の2倍が偶数になる3点の組」には、3点が一直線上に並んでいて面積が \(0\) になる組（ \(0\) は偶数なので条件を満たしてしまいます）も含まれています。 そのため、全体から「一直線上に並ぶ3点の組」の個数を引く必要があります。

\(N \le 3000\) であるため、3点の組み合わせを愚直に全探索すると \(O(N^3)\) となり実行時間制限に間に合いません。 しかし、1つの点 \(i\) を固定し、他の点 \(j\) への傾きを考えることで、この数え上げを \(O(N^2 \log N)\) に高速化できます。

---

アルゴリズム

ステップ1: 偶奇による分類と「面積の2倍が偶数」の数え上げ

1. 各点 \((X_i, Y_i)\) を \((X_i \bmod 2, Y_i \bmod 2)\) に基づいて4つのグループに分類し、それぞれの件数を記録します。
2. 4つのグループから3点を選ぶすべてのパターン（20通り）を探索します。
3. 各パターンについて、外積の偶奇が \(0\) になるならば、そのパターンにおける3点の選び方の総数（各グループの要素数を用いた組み合わせ数）を答えの候補に加算します。

ステップ2: 「一直線上にある3点」の数え上げ

3点 \(i, j, k\) が一直線上にあるとき、点 \(i\) を基準として、点 \(j\) への方向ベクトル \(\vec{v}_{ij}\) と点 \(k\) への方向ベクトル \(\vec{v}_{ik}\) の傾きが一致します。重複を避けるために \(i < j < k\) の順で数え上げます。

1. 各 \(i \, (1 \le i \le N)\) について、自身よりインデックスが大きいすべての点 \(j \, (i < j \le N)\) との差分ベクトル \((dx, dy) = (X_j - X_i, Y_j - Y_i)\) を求めます。
2. ベクトルの向きを揃えるため、 \(dx < 0\) または（ \(dx = 0\) かつ \(dy < 0\) ）の場合は、 \((dx, dy) \leftarrow (-dx, -dy)\) とします。
3. 最大公約数 \(g = \gcd(|dx|, |dy|)\) を求め、ベクトルを既約化（最簡整数比）した \((dx/g, dy/g)\) を傾きとして記録します。
4. 記録した傾きをソートしてグループ分けし、同じ傾きが \(c\) 個存在する場合、点 \(i\) を端点とする同一直線上の3点の組が \(\binom{c}{2}\) 個存在することになるため、これを足し合わせます。

ステップ3: 答えの算出

「面積の2倍が偶数になる3点の組の総数」から「一直線上にある3点の組の総数」を引いた値を出力します。

---

計算量

• 時間計算量: \(O(N^2 \log N)\)

  • 偶奇の分類と組み合わせ計算は \(O(N)\) です。
  • 一直線上の3点の数え上げにおいて、外側のループが \(N\) 回、内側のループが \(N\) 回回り、各ステップで \(\gcd\) の計算（ \(O(\log(\min(|dx|, |dy|)))\) ）と、傾きのソート（ \(O(N \log N)\) ）を行います。したがって、全体の時間計算量は \(O(N^2 \log N)\) となり、 \(N = 3000\) でも実行時間制限内に十分間に合います。

• 空間計算量: \(O(N)\)

  • 傾きを保持する配列のサイズは最大でも \(N\) であり、空間計算量は \(O(N)\) と非常に省メモリです。

---

実装のポイント

• 傾きの高速な管理: Pythonでタプル (dx // g, dy // g) をそのままリストに追加してソートすると、オブジェクトの生成や比較にオーバーヘッドが生じます。 正解コードでは、 \(dx // g\) と \(dy // g\) はそれぞれ32ビット整数に収まることを利用し、1つの64ビット整数にビットシフトを用いてパックしています（((dx // g) << 32) | ((dy // g) & 0xffffffff)）。これにより、ソートや比較が非常に高速に行われます。

  ソースコード

import sys
import math

def solve():
    # Fast I/O
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    X = [0] * N
    Y = [0] * N
    idx = 1
    for i in range(N):
        X[i] = int(input_data[idx])
        Y[i] = int(input_data[idx+1])
        idx += 2
        
    # Count parity patterns of coordinates
    counts = [0] * 4
    for i in range(N):
        px = X[i] % 2
        py = Y[i] % 2
        counts[px * 2 + py] += 1
        
    # Total combinations where 2S = 0 (mod 2)
    total_even_area = 0
    patterns = [
        (0, 0),
        (0, 1),
        (1, 0),
        (1, 1)
    ]
    
    def comb2(n):
        return n * (n - 1) // 2 if n >= 2 else 0
        
    def comb3(n):
        return n * (n - 1) * (n - 2) // 6 if n >= 3 else 0

    for i in range(4):
        for j in range(i, 4):
            for k in range(j, 4):
                x1, y1 = patterns[i]
                x2, y2 = patterns[j]
                x3, y3 = patterns[k]
                D = (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)
                if D % 2 == 0:
                    if i == j == k:
                        ways = comb3(counts[i])
                    elif i == j:
                        ways = comb2(counts[i]) * counts[k]
                    elif j == k:
                        ways = counts[i] * comb2(counts[j])
                    else:
                        ways = counts[i] * counts[j] * counts[k]
                    total_even_area += ways

    # Count collinear triplets
    collinear_count = 0
    gcd = math.gcd
    
    for i in range(N):
        xi = X[i]
        yi = Y[i]
        slopes = []
        for j in range(i + 1, N):
            dx = X[j] - xi
            dy = Y[j] - yi
            if dx < 0 or (dx == 0 and dy < 0):
                dx = -dx
                dy = -dy
            g = gcd(dx, dy if dy >= 0 else -dy)
            # Pack (dx//g, dy//g) into a single 64-bit integer for fast sorting
            slopes.append(((dx // g) << 32) | ((dy // g) & 0xffffffff))
            
        slopes.sort()
        n_slopes = len(slopes)
        if n_slopes < 2:
            continue
            
        curr_cnt = 1
        prev = slopes[0]
        for k in range(1, n_slopes):
            curr = slopes[k]
            if curr == prev:
                curr_cnt += 1
            else:
                if curr_cnt >= 2:
                    collinear_count += curr_cnt * (curr_cnt - 1) // 2
                curr_cnt = 1
                prev = curr
        if curr_cnt >= 2:
            collinear_count += curr_cnt * (curr_cnt - 1) // 2

    print(total_even_area - collinear_count)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。