概要

平面上の \(N\) 個の点から3点を選び、「一直線上に並んでいない（面積が正）」かつ「三角形の面積が整数である」ような選び方の数を求める問題です。

考察

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

3点 \(A(X_A, Y_A), B(X_B, Y_B), C(X_C, Y_C)\) を頂点とする三角形の面積 \(S\) は、外積を用いて以下のように表されます。 $\(2S = |(X_B - X_A)(Y_C - Y_A) - (X_C - X_A)(Y_B - Y_A)|\)$

面積 \(S\) が整数であることは、外積 \(2S\) が偶数（\(2S \equiv 0 \pmod 2\)）であることと同値です。 この式の偶奇（\(\bmod 2\)）のみに注目すると、各点の座標の偶奇タイプ \((X_i \bmod 2, Y_i \bmod 2)\) は以下の4パターンのいずれかになります。 - タイプ0: (偶数, 偶数) - タイプ1: (偶数, 奇数) - タイプ2: (奇数, 偶数) - タイプ3: (奇数, 奇数)

3点を選ぶとき、これらの偶奇タイプの組み合わせによって面積が整数になるかどうかが決まります。 実は、以下の非常にシンプルな性質が成り立ちます。 - 3点の偶奇タイプがすべて異なる場合のみ、面積は半整数（非整数）になる。 - それ以外（同じ偶奇タイプの点が2点以上含まれる）の場合、面積は必ず整数になる。

したがって、「面積が整数になる3点の選び方」は、全体から余事象を引くことで以下のように求められます。 $\(\text{(面積が整数になる選び方)} = \binom{N}{3} - \text{(異なる3つの偶奇タイプから1点ずつ選ぶ方法の数)}\)$

これは、各偶奇タイプに属する点の個数をカウントしておくことで、\(O(N)\) で計算可能です。

2. 一直線上に並ぶ3点（面積0）の除外

上記の計算には、3点が一直線上に並んで面積が \(0\)（整数）になる場合が含まれてしまっています。問題文の条件は「面積が正」であるため、一直線上に並ぶ3点の組の個数を求めて差し引く必要があります。

素朴に3点の組を全探索すると \(O(N^3)\) となり、\(N \le 3000\) では実行時間制限に間に合いません。そのため、一直線上に並ぶ3点を \(O(N^2 \log N)\) で効率的にカウントする必要があります。

アルゴリズム

ステップ1: 面積が整数になる3点の個数の計算

1. 各点の座標の偶奇に応じて、4つのバケット \(C[0][0], C[0][1], C[1][0], C[1][1]\) に分類し、それぞれの個数をカウントします。
2. 全体の選び方 \(\binom{N}{3}\) から、異なる3つのバケットから1点ずつ選ぶ方法の総数（4通り）を引くことで、「面積が整数になる3点の選び方の数」を求めます。

ステップ2: 一直線上に並ぶ3点の個数の計算

重複なく数え上げるために、以下の手順を踏みます。 1. 点の配列 \(P\) を辞書順（\(x\) 座標が小さい順、同じなら \(y\) 座標が小さい順）にソートします。 2. 各点 \(i\) を「一直線上の最も左（辞書順最小）の点」として固定します。 3. 点 \(i\) から、自分より辞書順で後ろにあるすべての点 \(j > i\) への方向ベクトル \((\Delta x, \Delta y)\) を計算します。 - \(\Delta x = X_j - X_i\) - \(\Delta y = Y_j - Y_i\) 4. 方向ベクトルを既約にするため、最大公約数 \(g = \gcd(|\Delta x|, |\Delta y|)\) で割ります。 - \(dx = \Delta x / g\) - \(dy = \Delta y / g\) 5. 得られた既約方向ベクトル \((dx, dy)\) をすべて集めてソートし、同じ方向ベクトルが何個連続しているかをカウントします。 6. 同じ方向ベクトルが \(k\) 個存在する場合、点 \(i\) とともに一直線上に並ぶ3点の組が \(\binom{k}{2}\) 個作れるため、これを答えに加算します。

ステップ3: 最終的な答えの計算

\[\text{答え} = \text{(面積が整数になる3点の数)} - \text{(一直線上に並ぶ3点の数)}\]

これを出力します。

計算量

• 時間計算量: \(O(N^2 \log N)\) 各点 \(i\) について、残り \(N-i\) 個の点との方向ベクトルを計算してソートする処理がボトルネックとなります。ソートには \(O(N \log N)\) かかり、これを \(N\) 回繰り返すため、全体で \(O(N^2 \log N)\) となります。\(N = 3000\) のとき \(N^2 \log N \approx 10^8\) 程度の計算量となり、C++などの高速な言語では実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\) 点の一覧や、各ステップで一時的に方向ベクトルを格納する配列のサイズは最大でも \(N\) です。

実装のポイント

• 方向ベクトルの高速なソート（ビットパック）: 方向ベクトルを構造体や std::pair で管理してソートするよりも、64ビット整数（unsigned long long）のビット列に \(dx\) と \(dy\) をパックして1つの数値として扱うことで、ソートのオーバーヘッドを大幅に削減し、高速化を図っています。 具体的には、\(-2 \times 10^9 \le dy \le 2 \times 10^9\) であるため、十分に安全なオフセット（2000000005LL）を足して非負にした上で、以下のように32ビットずつにパックします。 (udx << 32) | udy

• 辞書順ソートによる方向の正規化: 点をあらかじめ辞書順ソートしておくことで、自分より後ろの点への方向ベクトルを計算する際、必ず \(dx \ge 0\)（\(dx = 0\) のときは \(dy > 0\)）となり、方向ベクトルの符号の正規化が極めてシンプルになります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

struct Point {
    long long x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<Point> P(N);
    long long C[2][2] = {0};
    for (int i = 0; i < N; ++i) {
        cin >> P[i].x >> P[i].y;
        long long rx = (P[i].x % 2 + 2) % 2;
        long long ry = (P[i].y % 2 + 2) % 2;
        C[rx][ry]++;
    }

    // 辞書順でソート
    sort(P.begin(), P.end());

    long long total_triangles = (long long)N * (N - 1) * (N - 2) / 6;

    // 異なる3つの偶奇タイプを選ぶ方法の数
    long long diff_3 = 0;
    diff_3 += C[0][0] * C[0][1] * C[1][0];
    diff_3 += C[0][0] * C[0][1] * C[1][1];
    diff_3 += C[0][0] * C[1][0] * C[1][1];
    diff_3 += C[0][1] * C[1][0] * C[1][1];

    // 面積が整数になる3点の選び方の数
    long long integer_area_selections = total_triangles - diff_3;

    // 一直線上に並ぶ3点の選び方の数
    long long collinear_count = 0;
    vector<unsigned long long> vecs;
    vecs.reserve(N);

    for (int i = 0; i < N; ++i) {
        vecs.clear();
        for (int j = i + 1; j < N; ++j) {
            long long dx = P[j].x - P[i].x;
            long long dy = P[j].y - P[i].y;
            long long g = std::gcd(std::abs(dx), std::abs(dy));
            dx /= g;
            dy /= g;
            
            // dx >= 0, dy は [-2e9, 2e9]
            // dy にオフセットを足して非負にし、32ビットずつにパックして高速にソートできるようにする
            unsigned long long udx = dx;
            unsigned long long udy = dy + 2000000005LL;
            vecs.push_back((udx << 32) | udy);
        }
        sort(vecs.begin(), vecs.end());
        
        long long temp_count = 1;
        for (size_t k = 1; k < vecs.size(); ++k) {
            if (vecs[k] == vecs[k - 1]) {
                temp_count++;
            } else {
                collinear_count += temp_count * (temp_count - 1) / 2;
                temp_count = 1;
            }
        }
        if (!vecs.empty()) {
            collinear_count += temp_count * (temp_count - 1) / 2;
        }
    }

    // (面積が整数の3点) - (一直線上の3点) = (面積が正かつ整数の三角形)
    long long ans = integer_area_selections - collinear_count;
    cout << ans << "\n";

    return 0;
}

---

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