# Max Points on a Line

犯的错：双层for循环，max只用来记录内层循环里 点的个数，在外层循环里才是记录最后返回结果。另外 嵌套map注意

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

参照leetcode大神的解法：<https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes>

运用最大公约数来解决求斜率的除法中小数不精确的问题

用了嵌套map的方法，把对应两点的x距离，和y距离分别作为嵌套map的key存储起来，注意这里的x和y是剔除了最大公约数以后的，也就是说，同一条线上的两个点经过剔除最大公约数的操作后，x，和y应该是相同的，存入map后，最里层map的value就是最外层遍历当前的点和其后面所有点在同一条线的个数。注意overlap的数目，overlap也算是在同一条线

```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; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        if(points == null || points.length == 0){
            return 0;
        }
        
        if(points.length <= 2)
            return points.length;
        
        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<Integer,HashMap<Integer,Integer>>();
        int result = 0;
        for(int i = 0; i < points.length; i++){
            map.clear();
            int overlap = 0, max = 0;
            for(int j = i+1; j < points.length; j++){
                int x = points[j].x-points[i].x;
                int y = points[j].y-points[i].y;
                
                if(x == 0 && y == 0){
                    overlap++;
                    continue;
                }
                
                int gcd = getGCD(x,y);
                
                if(gcd != 0){
                    x /=gcd;
                    y /= gcd;
                }
                
                if(map.containsKey(x)){
                    if(map.get(x).containsKey(y)){
                        map.get(x).put(y,map.get(x).get(y)+1);
                    }else{
                       map.get(x).put(y,1);
                    }
                }else{
                     HashMap<Integer,Integer> subMap = new HashMap<>();
                        
                        subMap.put(y,1);
                        map.put(x,subMap);
                }
                
                max = Math.max(max,map.get(x).get(y));
            }
            
            result = Math.max(result,max+overlap+1);
        }
        
        return result;
    }
    
    public int getGCD(int x,int y){
        if(y == 0)
            return x;
        else return getGCD(y,x%y);
    }
}
```


---

# 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://shuati.gitbook.io/crack-lintcode/linkedin/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.