題目描述:給定一個平面上的 n 個點,找出最多有多少個點共線(即位於同一條直線上)。
解題思路:對每個點 P 作為「錨點」,計算它與其他所有點的斜率,斜率相同的點必然共線。斜率用分數 (dy/gcd, dx/gcd) 來表示以避免浮點誤差,其中 dy = y2 - y1、dx = x2 - x1,並且分母統一保持非負。以 unordered_map 記錄每種斜率出現的次數,取最大值即為通過 P 的最多共線點數(記得加上 P 本身)。重複點(dx = 0, dy = 0)單獨計數,加入每種斜率結果中。最終答案取所有錨點所得最大值。
時間複雜度:O(n²) — 外層遍歷每個錨點 O(n),內層計算所有斜率 O(n);__gcd 為 O(log V),整體為 O(n² log V),題目約束 n ≤ 300 故可接受。
空間複雜度:O(n) — 每次錨點迭代使用的 hash map 最多存 n 個不同斜率,結束後清除。
1. If n <= 2, return n immediately.
2. Initialize ans = 2.
3. For each point i as anchor:
a. Create slopeMap (slope -> count), duplicates = 0, localMax = 0.
b. For each point j > i:
- Compute dx = x[j]-x[i], dy = y[j]-y[i].
- If dx==0 and dy==0: duplicates++, continue.
- g = gcd(|dx|, |dy|); dx /= g; dy /= g.
- Normalize sign so dx >= 0.
- Encode (dx, dy) as a single integer key.
- Increment slopeMap[key]; update localMax.
c. ans = max(ans, localMax + duplicates + 1).
4. Return ans.方法一:暴力枚舉直線 O(n³) 對每對點 (i, j) 定義一條直線,再遍歷所有其他點判斷是否在該線上。時間複雜度 O(n³),空間 O(1),適合 n 極小的場合,但不實用。
方法二:分數斜率 Hash Map(本題主解)O(n²) 對每個錨點,以化簡分數 (dy/gcd, dx/gcd) 作為 hash key,統計各斜率出現次數。避免浮點誤差,時間 O(n² log V),空間 O(n)。
方法三:浮點數斜率 Hash Map O(n²) 直接用 double 斜率作為 key。實作簡單但有浮點精度風險,在特殊測資下可能錯誤,不推薦用於 competitive programming。