# 149. Max Points on a Line

#### Hard

***

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the **X-Y** plane, return *the maximum number of points that lie on the same straight line*.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg)

```
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg)

```
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
```

 

**Constraints:**

* `1 <= points.length <= 300`
* `points[i].length == 2`
* `-104 <= xi, yi <= 104`
* All the `points` are **unique**.

```python
from collections import defaultdict
import math

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        result = 0
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                count = 0
                for k in range(len(points)):
                    count += self.check_line(points[i], points[j], points[k])
                result = max(result, count)
        return 1 if result == 0 else result
                    
    def check_line(self, p1, p2, p3):
        if (p1[0]- p3[0])*(p2[1]-p3[1]) == (p1[1]- p3[1])*(p2[0]- p3[0]):
            return 1
        else:
            return 0
 
```