To solve this problem, we need to count the number of triangles that can be formed using points on an H x W grid, excluding those triplets of points that are collinear.
Approach
- Total Triplets: Calculate the total number of ways to choose 3 points from the grid. This is given by the combination formula (C(N,3)) where (N = H \times W).
- Collinear Triplets: Subtract the number of collinear triplets from the total triplets. Collinear triplets are of three types:
- Horizontal: Triplets lying on the same row.
- Vertical: Triplets lying on the same column.
- Diagonal: Triplets lying on lines with non-zero and non-infinite slopes. For these, we consider lines with coprime direction vectors (dx, dy) and count valid segments.
Solution Code
import math
def count_triangles(H, W):
total_points = H * W
total = total_points * (total_points - 1) * (total_points - 2) // 6 if total_points >=3 else 0
# Horizontal collinear triplets
horizontal = H * (W * (W -1) * (W -2) // 6) if W >=3 else 0
# Vertical collinear triplets
vertical = W * (H * (H -1) * (H -2) //6) if H >=3 else 0
# Diagonal collinear triplets (slope non-zero and non-infinite)
diag = 0
for dx in range(1, W):
for dy in range(1, H):
if math.gcd(dx, dy) !=1:
continue
t_max = min((W-1) // dx, (H-1) // dy)
for t in range(2, t_max + 1):
cnt = (W - dx * t) * (H - dy * t)
triplets = cnt * ((t+1)*t*(t-1) // 6)
diag += triplets
diag *=2 # for both positive and negative slopes
total -= (horizontal + vertical + diag)
return total
# Read input
H, W = map(int, input().split())
print(count_triangles(H, W))
Explanation
- Total Triplets: The formula (C(N,3)) gives the number of ways to choose any three points from the grid.
- Horizontal & Vertical: For each row (or column), the number of collinear triplets is (C(W,3)) (or (C(H,3))) multiplied by the number of rows (or columns).
- Diagonals: For each coprime direction vector (dx, dy), we calculate the maximum number of steps (t) such that the segment stays within the grid. For each valid segment length (t+1 points), the number of triplets is (C(t+1,3)) multiplied by the number of such segments. This is doubled to account for both positive and negative slopes.
This approach efficiently counts all valid triangles by excluding collinear triplets, ensuring correctness and optimal performance for typical grid sizes.


作者声明:本文包含人工智能生成内容。