# [149\. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)

直線的公式：`y = ax + b`
特殊情況：
- 兩個點重疊的情況。
- 兩個點在 x 軸上重合的狀況，如果 $(x_2 - x_1)$ 為 0，則沒辦法計算斜率。

對於兩個點 $(x_1, y_1)$ 和 $(x_2, y_2)$ 計算斜率 `k` 的公式：$k = (y_2 - y_1) / (x_2 - x_1)$

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        
        // 保存經過相同直線的最多點的數量
        int maxSlope = 0;
        
        // 保存斜率與點個數的 mapping
        // {斜率: 通過的點個數}
        unordered_map<double, int> m;
        
        // 使用兩個迴圈走訪兩個 points
        for (int i = 0 ; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // point1(x1, y1)
                double x1 = points[j][0];
                double y1 = points[j][1];

                // point2(x2, y2)
                double x2 = points[i][0];
                double y2 = points[i][1];

                if(y2 == y1 && x2 == x1)
                {
                    // 如果兩個點重疊，則跳過這個點
                    continue;
                }
                else if (x2 == x1)
                {
                    // 如果兩個點在 x 軸上重合
                    // 斜率為 INT_MAX
                    m[INT_MAX]++;
                }
                else
                {
                    // 其他的狀況才可以套用斜率公式
                    double slope = (y2 - y1) / (x2 - x1);
                    // 對於相同的斜率，點的個數 + 1
                    m[slope]++;
                }
            }

            // 對於每個點，走訪 m 並找到最多點的斜率，並將其保存到 curMax 中。
            int curMax = 0;
            for (auto a : m)
            {
                curMax = max(curMax, a.second);
            }
            maxSlope = max(maxSlope, curMax);
            
            // 清空 hashMap，計算下一次的組合
            m.clear();
        }
        // 最後回傳 maxSlope + 1，因為需要考慮到自己本身
        return maxSlope + 1;
    }
};

:::success
- 時間複雜度：$O(n^2)$
- 空間複雜度：$O(n)$
:::