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

### 題目描述

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

### 範例

**Example 1:**


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

**Example 2:**


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
* -10^4^ <= $x_i$, $y_i$ <= 10^4^
* All the `points` are **unique**.

### 解答

#### Python

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ans = 0
        for i, (x1, y1) in enumerate(points):
            count = defaultdict(int)
            for x2, y2 in points[i+1:]:
                dx, dy = x1 - x2, y1 - y2
                if dy < 0 or (dy == 0 and dx < 0):
                    dx, dy = -dx, -dy
                g = gcd(dx, dy)
                slope = dx // g, dy // g
                count[slope] += 1
            ans = max(ans, max(count.values(), default=0))
        return ans + 1

> [name=Yen-Chi Chen][time=Sun, Jan 8, 2023]

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        return max([max(Counter([(dx // gcd(dx, dy), dy // gcd(dx, dy)) for dx, dy in [(-Dx, -Dy) if Dy < 0 or (Dy == 0 and Dx < 0) else (Dx, Dy) for Dx, Dy in [(x1 - x2, y1 - y2) for x2, y2 in points[i+1:]]]]).values(), default=0) for i, (x1, y1) in enumerate(points)]) + 1

> [name=Yen-Chi Chen][time=Sun, Jan 8, 2023]

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        res = 0

        for i, (x1, y1) in enumerate(points):
            same_point = 1
            cnt = defaultdict(int)
            for x2, y2 in points[i+1:]:
                if x1 == x2 and y1 == y2:
                    same_point += 1
                elif x1 == x2:
                    cnt[math.inf] += 1
                else:
                    slope = (y1 - y2) / (x1 - x2)
                    cnt[slope] += 1

            local_max = max(cnt.values(), default=0) + same_point
            res = max(res, local_max)

        return res

> [name=Ron Chen][time=Mon, Jan 9, 2023]

#### Javascript

function maxPoints(points) {
  if (points.length < 3) return points.length;

  let max = 0;

  // 紀錄每兩個點的斜率
  for (let i = 0; i < points.length; i++) {
    const map = new Map();
    let localMax = 1;
    for (let j = i + 1; j < points.length; j++) {
      const [x1, y1] = points[i];
      const [x2, y2] = points[j];
      const slope = getSlope(x1, y1, x2, y2);

      map.set(slope, map.has(slope) ? map.get(slope) + 1 : 2);
      localMax = Math.max(localMax, map.get(slope));
    }

    max = Math.max(max, localMax);
  }

  return max;
}

function getSlope(x1, y1, x2, y2) {
  if (x1 === x2) return null;
  if (y1 === y2) return 0;
  return (y2 - y1) / (x2 - x1);
}

> [name=Marsgoat][time=Jul 6, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)