/*
* A line is determined by two factors,say y=ax+b
*
* If two points(x1,y1) (x2,y2) are on the same line(Of course).
* Consider the gap between two points.
* We have (y2y1)=a(x2x1),a=(y2y1)/(x2x1) a is a rational, b is canceled since b is a constant
* If a third point (x3,y3) are on the same line. So we must have y3=ax3+b
* Thus,(y3y1)/(x3x1)=(y2y1)/(x2x1)=a
* Since a is a rational, there exists y0 and x0, y0/x0=(y3y1)/(x3x1)=(y2y1)/(x2x1)=a
* So we can use y0&x0 to track a line;
*/
public class Solution{
public int maxPoints(Point[] points) {
if (points==null) return 0;
if (points.length<=2) return points.length;
Map<Integer,Map<Integer,Integer>> map = new HashMap<Integer,Map<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].xpoints[i].x;
int y=points[j].ypoints[i].y;
if (x==0&&y==0){
overlap++;
continue;
}
int gcd=generateGCD(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{
Map<Integer,Integer> m = new HashMap<Integer,Integer>();
m.put(y, 1);
map.put(x, m);
}
max=Math.max(max, map.get(x).get(y));
}
result=Math.max(result, max+overlap+1);
}
return result;
}
private int generateGCD(int a,int b){
if (b==0) return a;
else return generateGCD(b,a%b);
}
}
A java solution with notes


One c++ solution with the same idea.
class Solution{ public: int maxPoints(vector<Point> &points){ if (points.size()<=2) return points.size(); map<int,map<int,int> > map; int result=0; for (unsigned int i=0;i<points.size();i++){ map.clear(); int localmax=0,overlap=0; for (unsigned int j=i+1;j<points.size();j++){ int x=points[j].xpoints[i].x; int y=points[j].ypoints[i].y; //check overlap if (x==0&&y==0){ overlap++; continue; } int gcd=generateGCD(x,y); if (gcd!=0){ x/=gcd; y/=gcd; } //find x,then y; int curr=++map[x][y]; localmax=max(curr,localmax); } result=max(result,localmax+overlap+1); } return result; } private: int generateGCD(int a, int b){ if (b==0) return a; return generateGCD(b,a%b); } };

I think it will not work in below case. If points lie on two different parallel lines, it will consider as all points lie on same line.
Suppose consider points (2,4), (2,6), (4,4), (4,6).
We know that (2,4) and (2,6) lie on line X =2
and (4,4), (4,6) lies on line X = 4for (2,4) and (2,6)
from your method x = 22, y = 64, gcd(2,0) == 2for (4,4) and (4,6)
from your method x = 44, y = 64 gcd(2, 0) == 2All 4 points will end up getting stored in same location although those are on 2 different paraller lines