Max Points on a Line：哈希斜率統計共線點最大數

問題

給定平面 n 點，求最多有多少點在同一直線上。

核心思路：以每點為基準統計斜率

固定點 i，計算其他點 j 相對 i 的斜率 dy/dx。用最大公約數約分並統一符號（dx<0 時同號翻轉，dx=0 或 dy=0 取絕對值），以 (dx/g, dy/g) 作為鍵存入 HashMap 計數。同斜率計數 +1（含基點）即共線點數。處理重合點單獨計數。

Java 實現

public int maxPoints(Point[] points) {
    if (points.length <= 2) return points.length;
    int ans = 0;
    for (int i = 0; i < points.length; i++) {
        Map map = new HashMap<>();
        int same = 0, localMax = 0;
        for (int j = 0; j < points.length; j++) if (i != j) {
            int dx = points[j].x - points[i].x;
            int dy = points[j].y - points[i].y;
            if (dx == 0 && dy == 0) { same++; continue; }
            int g = gcd(Math.abs(dx), Math.abs(dy));
            dx /= g; dy /= g;
            if (dx < 0) { dx = -dx; dy = -dy; }
            if (dx == 0 || dy == 0) { dx = Math.abs(dx); dy = Math.abs(dy); }
            String key = dx + "," + dy;
            int cnt = map.getOrDefault(key, 0) + 1;
            map.put(key, cnt);
            localMax = Math.max(localMax, cnt);
        }
        ans = Math.max(ans, localMax + 1 + same);
    }
    return ans;
}
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }

複雜度

O(n²) 時間，O(n) 空間（每輪 HashMap）。n ≤ 300 時極快。注意 gcd(0,0) 未定義，重合點單獨處理。