public class Solution
{
public int maxPoints(Point[] points)
{
int n=points.length;
if (n<2) return n;
int currentL=0,maxL=2,x=0,y=0,dx=0,dy=0,overlap=0,upperB=n;
for(int i=0; i<upperB; i++)
{
for(int j=i+1; j<n; j++)
{
currentL=1;
/*
* Given two points: (a,b) and (c,d), the corresponding normal vector is (bd,ca)
* If another point (s,t) is in the same line uniquely defined by (a,b) and (c,d),
* then (sa,tb) dot (bd,ca) = 0
*/
x=points[i].ypoints[j].y;
y=points[j].xpoints[i].x;
/* If two points are the same, there is no need to check further,
* since a line has to be defined by exactly two distinct points.
*/
if(x==0 && y==0)
overlap++;
/* Well, it might be the case that duplicates are not consecutive,
* but as long as we can have a nontrivial normal vector, it won't matter.
*/
else
{
currentL++;
/* Explaining (currentL+nk>maxL):
* no further checking is necessary when there isn't enough left to make it surpass maxL.
*/
for(int k=j+1; k<n && currentL+nk>maxL; k++)
{
dx=points[k].xpoints[i].x;
dy=points[k].ypoints[i].y;
if(x*dx+y*dy==0)
currentL++;
}
}
maxL=Math.max(currentL+overlap,maxL);
}
/* Explaining (upperB=nmaxL):
* it would be crystal clear as soon as you draw a table for combinations of case n>3.
*/
upperB=nmaxL;
overlap=0;
}
return maxL;
}
}
My java accepted solution for your reference (only using array).


int maxPoints(vector<Point> &points) { int res=0; for(int i=0;i<points.size();i++){ int dup=1; map<double, int> mp; for(int j=i+1;j<points.size();j++){ if(points[i].x==points[j].x && points[i].y==points[j].y) dup++; else if(points[i].x==points[j].x) mp[INT_MAX]++; else{ double key=double(points[i].ypoints[j].y)/double(points[i].xpoints[j].x); mp[key]++; } } map<double, int>::iterator iter; int max=0; for(iter=mp.begin();iter!=mp.end();iter++) max=max<iter>second?iter>second:max; max+=dup; res=res<max?max:res; } return res; }
Here is my solution. It seems not that accurate in some floating point cases, but it works well on OJ. And it takes 80ms.
