Overview

Given \(N\) points on a plane, we need to find the number of ways to choose 3 points such that they are “not collinear (positive area)” and “the area of the triangle is an integer.”

Analysis

1. Condition for Integer Area

The area \(S\) of a triangle with vertices \(A(X_A, Y_A), B(X_B, Y_B), C(X_C, Y_C)\) can be expressed using the cross product as follows: $\(2S = |(X_B - X_A)(Y_C - Y_A) - (X_C - X_A)(Y_B - Y_A)|\)$

The area \(S\) being an integer is equivalent to the cross product \(2S\) being even (\(2S \equiv 0 \pmod 2\)). Focusing only on the parity (\(\bmod 2\)) of this expression, the parity type \((X_i \bmod 2, Y_i \bmod 2)\) of each point’s coordinates falls into one of the following 4 patterns: - Type 0: (even, even) - Type 1: (even, odd) - Type 2: (odd, even) - Type 3: (odd, odd)

When choosing 3 points, whether the area is an integer is determined by the combination of these parity types. In fact, the following very simple property holds: - Only when all three points have mutually different parity types does the area become a half-integer (non-integer). - In all other cases (when 2 or more points share the same parity type), the area is always an integer.

Therefore, “the number of ways to choose 3 points with integer area” can be computed by subtracting the complement from the total: $\(\text{(ways with integer area)} = \binom{N}{3} - \text{(number of ways to choose one point from each of 3 different parity types)}\)$

This can be computed in \(O(N)\) by counting the number of points belonging to each parity type.

2. Excluding Collinear Triples (Area 0)

The above calculation includes cases where 3 points are collinear with area \(0\) (which is an integer). Since the problem requires “positive area,” we need to compute and subtract the number of collinear triples.

Naively enumerating all triples takes \(O(N^3)\), which won’t fit within the time limit for \(N \le 3000\). Therefore, we need to efficiently count collinear triples in \(O(N^2 \log N)\).

Algorithm

Step 1: Counting Triples with Integer Area

1. Classify each point into one of 4 buckets \(C[0][0], C[0][1], C[1][0], C[1][1]\) based on the parity of its coordinates, and count the number in each.
2. Subtract from the total \(\binom{N}{3}\) the total number of ways to choose one point from each of 3 different buckets (4 combinations) to obtain “the number of ways to choose 3 points with integer area.”

Step 2: Counting Collinear Triples

To count without duplication, we follow these steps: 1. Sort the point array \(P\) in lexicographic order (by \(x\)-coordinate ascending, breaking ties by \(y\)-coordinate ascending). 2. Fix each point \(i\) as the “leftmost (lexicographically smallest) point” on the line. 3. For each point \(j > i\) that comes after \(i\) in lexicographic order, compute the direction vector \((\Delta x, \Delta y)\) from point \(i\). - \(\Delta x = X_j - X_i\) - \(\Delta y = Y_j - Y_i\) 4. To reduce the direction vector to its irreducible form, divide by the greatest common divisor \(g = \gcd(|\Delta x|, |\Delta y|)\). - \(dx = \Delta x / g\) - \(dy = \Delta y / g\) 5. Collect all resulting irreducible direction vectors \((dx, dy)\), sort them, and count how many consecutive identical direction vectors there are. 6. If there are \(k\) identical direction vectors, then \(\binom{k}{2}\) collinear triples can be formed together with point \(i\), so add this to the answer.

Step 3: Computing the Final Answer

\[\text{Answer} = \text{(number of triples with integer area)} - \text{(number of collinear triples)}\]

Output this value.

Complexity

• Time Complexity: \(O(N^2 \log N)\) The bottleneck is computing and sorting the direction vectors from each point \(i\) to the remaining \(N-i\) points. Sorting takes \(O(N \log N)\), and repeating this \(N\) times gives an overall complexity of \(O(N^2 \log N)\). For \(N = 3000\), \(N^2 \log N \approx 10^8\), which comfortably fits within the time limit in fast languages like C++.
• Space Complexity: \(O(N)\) The point list and the temporary arrays for storing direction vectors at each step have a maximum size of \(N\).

Implementation Notes

• Fast Sorting of Direction Vectors (Bit Packing): Rather than managing direction vectors as structs or std::pair and sorting them, we pack \(dx\) and \(dy\) into a 64-bit integer (unsigned long long) as a single numeric value, significantly reducing sorting overhead for better performance. Specifically, since \(-2 \times 10^9 \le dy \le 2 \times 10^9\), we add a sufficiently safe offset (2000000005LL) to make it non-negative, then pack into 32 bits each as follows: (udx << 32) | udy

• Direction Normalization via Lexicographic Sort: By pre-sorting points in lexicographic order, when computing direction vectors to subsequent points, we always have \(dx \ge 0\) (and \(dy > 0\) when \(dx = 0\)), making the sign normalization of direction vectors extremely simple.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.