Overview

A problem to find the number of ways to choose 3 points from \(N\) points such that the triangle formed has a positive integer area. The integer area condition is reduced to the “parity of the cross product,” and the answer is efficiently computed using classification by coordinate parity and exclusion of collinear points.

Analysis

Area Formula and Integer Condition

The area of a triangle with vertices \((x_i, y_i), (x_j, y_j), (x_k, y_k)\) is:

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

Let the cross product part be \(C = (x_j - x_i)(y_k - y_i) - (x_k - x_i)(y_j - y_i)\). The conditions are:

1. Positive area: \(C \neq 0\) (the 3 points are not collinear)
2. Integer area: \(C\) is even (\(|C|/2\) is an integer)

In other words, we want to count the number of triples where “\(C\) is even and \(C \neq 0\)”.

Problem with the Naive Approach

Checking all triples of points takes \(O(N^3)\), and for \(N = 3000\), \(N^3 \approx 2.7 \times 10^{10}\), which results in TLE.

Key Insight: Classification by Parity

The parity of \(C\) depends only on each coordinate \(\mod 2\). That is:

\[(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\) is XOR, \(\land\) is AND)

By classifying each point into 4 types based on \((x \bmod 2, y \bmod 2)\), we can determine whether the cross product is even for each type combination (at most \(\binom{4+2}{3} = 20\) combinations) and compute the number of corresponding triples using combinatorics.

Algorithm

Step 1: Count triples with even cross product

1. Classify each point into 4 types by \((x \bmod 2, y \bmod 2)\) and compute the count of each type \(cnt[0], cnt[1], cnt[2], cnt[3]\).
2. For all type combinations \((t_a, t_b, t_c)\) (\(t_a \leq t_b \leq t_c\)), determine whether the cross product parity is 0.
3. If it is 0, calculate the number of triples from the corresponding point counts and add them.
   • All 3 same type: \(\binom{cnt[t]}{3}\)
   • 2 same type: \(\binom{cnt[t_a]}{2} \times cnt[t_c]\), etc.
   • All 3 different types: \(cnt[t_a] \times cnt[t_b] \times cnt[t_c]\)

Step 2: Count collinear triples (to subtract)

Collinear triples (cross product is 0) are also included in “even cross product,” so we need to subtract them.

• For each point \(i\), normalize the direction vector \((dx, dy)\) to all other points \(j\) by dividing by GCD, and manage them using a dictionary.
• The number of pairs with the same direction \(\binom{v}{2}\) (\(v\) is the number of points in the same direction) gives the number of collinear triples containing point \(i\).
• Summing over all \(i\), each collinear triple is counted exactly once (because we fix the point with the smallest index).

Final Result: \(\text{even\_count} - \text{collinear}\)

Complexity

• Time complexity: \(O(N^2)\) (dominated by the collinear check in Step 2)
• Space complexity: \(O(N)\) (direction vector dictionary for each point)

Implementation Notes

• Direction vector normalization: Divide \((dx, dy)\) by GCD, and further unify the sign (negate if \(dx < 0\); if \(dx = 0\), ensure \(dy > 0\)). This ensures that points on the same line map to the same key.

• Type classification: Assign to 0–3 using (x % 2) * 2 + (y % 2). Python’s % returns non-negative results even for negative numbers, so it is safe.

• Cross product parity check: Can be concisely written using bit operations (XOR, AND).

• i < j constraint: In counting collinear triples, by only looking at points \(j\) with larger indices from each point \(i\), we prevent duplicate counting of triples.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.