UVA 12075 Counting Triangles：網格中格點三角形計數與容斥原理

UVA 12075 Counting Triangles：M×N 網格格點三角形計數

題意：給定 M, N (≤ 1000)，求 (M+1)×(N+1) 整數格點中，能構成非退化三角形（面積 > 0）的三元組數量。結果保證適合 64 位有號整數。

總體思路：總組合數 − 共線三點組合數

總點數 P = (M+1)*(N+1)。任意三點組合數 C(P,3)。需扣除三點共線的情況：

1. 水平共線：N+1 行，每行 M+1 點 → (N+1)*C(M+1,3)
2. 垂直共線：M+1 列，每列 N+1 點 → (M+1)*C(N+1,3)
3. 斜線共線：核心難點，需容斥原理 + 動態規劃。

斜線共線計數：DP + 容斥

考慮向量 (dx, dy)，dx, dy > 0。若 gcd(dx, dy) = g，則該方向上每 g 個格點共線。從 (0,0) 到 (i,j) 的線段上（含端點）有 gcd(i,j)+1 個格點，即 gcd(i,j)-1 個內部點。
定義 dp[i][j] 為從 (0,0) 到 (i,j) 矩形區域內，以 (0,0) 和 (i,j) 為端點的三點共線數（即 gcd(i,j)-1）。
則 N×M 網格總斜線共線三元組數為：

ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + dp[i][j]

最終總共線三元組 = 水平 + 垂直 + 2 * ans[M][N]（乘 2 因對稱：左上→右下與左下→右上）。

完整 AC 代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
typedef long long ll;
using namespace std;
const int MAXN = 1010;
ll dp[MAXN][MAXN], ans[MAXN][MAXN];
int n, m;

int gcd(int a, int b) { return b==0?a:gcd(b, a%b); }

void init() {
    memset(dp, 0, sizeof(dp));
    memset(ans, 0, sizeof(ans));
    for (int i=1; i

關鍵點總結

預計算 dp 和 ans 至 1000，查詢 O(1)。
gcd(i,j)-1 代表向量 (i,j) 方向的內部格點數。
二維前綴和（容斥）快速聚合矩形區域貢獻。
最終乘 2 處理對稱斜線方向。

本題展示了組合數學、數論（gcd）、動態規劃（二維前綴和）的完美結合，是格點幾何計數的經典範例。