# 149.Max-Points-on-a-Line

## 149. Max Points on a Line

## 题目地址

<https://leetcode.com/problems/max-points-on-a-line/>

## 题目描述

```
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

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.
```

## 代码

### Approach #1 Enumeration

`Time O(N^2) Space O(N)`

```java
class Solution {
  int[][] points;
  int n;
  HashMap<Double, Integer> lines = new HashMap<Double, Integer>();
  int horizontal_lines;

  public int maxPoints(int[][] points) {
        this.points = points;
    n = points.length;
    if (n < 3)        return n;

    int max_count = 1;
    for (int i = 0; i < n - 1; i++) {
      max_count = Math.max(max_points_on_a_line_containing_point_i(i), max_count);
    }
    return max_count;
  }

  public int max_points_on_a_line_containing_point_i(int i) {
    lines.clear();
    horizontal_lines = 1;
    int count = 1;
    int duplicates = 0;

    for (int j = i + 1; j < n; j++) {
      Pair<Integer, Integer> p = add_line(i, j, count, duplicates);
      count = p.getKey();
      duplicates = p.getValue();
    }
    return count + duplicates;
  }

    public Pair<Integer, Integer> add_line(int i, int j, int count, int duplicates) {
    int x1 = points[i][0];
    int y1 = points[i][1];
    int x2 = points[j][0];
    int y2 = points[j][1];
    if (x1 == x2 && y1 == y2) {
      duplicates++;
    } else if (y1 == y2) {
      horizontal_lines += 1;
      count = Math.max(horizontal_lines, count);
    } else {
      double slope = 1.0 * (x1 - x2) / (y1 - y2) + 0.0;
      lines.put(slope, lines.getOrDefault(slope, 1) + 1);
      count = Math.max(lines.get(slope), count);
    }
    return new Pair(count, duplicates);
  }
}
```

### #2

```java
  /**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length <= 0) return 0;
        if(points.length <= 2) return points.length;
        int result = 0;
        for(int i = 0; i < points.length; i++){
            HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
            int samex = 1;
            int samep = 0;
            for(int j = 0; j < points.length; j++){
                if(j != i){
                    if((points[j].x == points[i].x) && (points[j].y == points[i].y)){
                        samep++;
                    }
                    if(points[j].x == points[i].x){
                        samex++;
                        continue;
                    }
                    double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
                    if(hm.containsKey(k)){
                        hm.put(k,hm.get(k) + 1);
                    }else{
                        hm.put(k, 2);
                    }
                    result = Math.max(result, hm.get(k) + samep);
                }
            }
            result = Math.max(result, samex);
        }
        return result;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/other/149.max-points-on-a-line.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.