# LeetCode - 149.Max Points on a Line
###### tags: `LeetCode` `Guide` `C++` `Hard`
> 原題連結: https://leetcode.com/problems/max-points-on-a-line/

> Difficulty: <span style="color: red;">Hard</span>

<br/>

## 題目說明
### 原文
Given **n** points on a 2D plane, find the **maximum** number of points that lie on the same straight line.

### 翻譯
給定**n**個2D平面上的點，找出所有可能的共線中，含有點**最多**的**點個數**。

<br/>

## 範例測資
### Example 1.
#### Input:

[[1,1],[2,2],[3,3]]

#### Output:

3

#### Explanation:

^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

### Example 2.
#### Input:

[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

#### Output:

4

#### Explanation:

^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

### Note
input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

<br/>

## Code與解析
### 作法1. Brute Force <span style="font-size:5px; color:orange;">[TimeLimitExceed]</span>
基本上一定會超時，所以我就不做了。
簡單來說就是分別找2個點，然後把其他點全部檢查一次，時間複雜度會是```O(n^3)```
### 作法2. Optimal Solution <span style="font-size:5px; color:green;">[Accept]</span>
> Runtime: 12 ms > 98.24%
> Memory: 9.2 MB > 78.57%

class Solution {
   public:
    int maxPoints(vector<vector<int>>& points) {
        // If points' amount equal or less than 2, answer is points' amount.
        if (points.size() <= 2) return points.size();

        map<double, int> slopes;  // Saving the counts in same slope.
        int res = 2;
        while (points.size() > 2) {
            int vertical = 1;
            // Choose the last point in the list.
            int x = points[points.size() - 1][0];
            int y = points[points.size() - 1][1];
            slopes.clear();
            int tempRst = 0;
            int overlapped = 0;
            // Check with every other point.
            for (int i = points.size() - 2; i >= 0; i--) {
                if (points[i][0] == x && points[i][1] != y)
                    ++vertical;                                     // Check point on vertical line.
                else if (points[i][0] == x && points[i][1] == y) {  // Check overlapped point.
                    ++overlapped;
                    points.erase(points.begin() + i);  // It's the same point, so we just need to check it once, skip it anyway.
                } else
                    ++slopes[((double)(points[i][1] - y) / (points[i][0] - x))];
            }
            for (auto& i : slopes)
                if (++i.second > tempRst) tempRst = i.second;                    // Find the maximum result of this point.
            tempRst = ((tempRst > vertical) ? tempRst : vertical) + overlapped;  // Same as above.
            res = max(res, tempRst);                                             // Is this the most result so far?
            points.pop_back();                                                   // This point already checked, so skip it anyway.
        }
        return res;
    }
};

這個做法很像暴力破解，但是用了一點技巧。
首先，每次的迭代只找一個點，並且輪流跟其他點計算斜率。(程式碼Line18~26的部分。)
這樣一來，我可以確定把選定的這個點相關的所有線都找完。
並且，從3點共線的定義：

1. **此線通過選定點**。
2. **共線的點之間互連的直線斜率必定相同**。

可以反推回去。
又因為一次迭代就會把關於這個選定點的直線檢查完，所以在計算後可以先刪除。
之後每次迭代就只需要檢查剩餘的點即可。