Any better solution than O(n^2) ?
Pick 2 points from n. generate a line y=kx+b; store <k,b> in a hashset.
I have the similar idea, but I got two questions:
Thanks a lot!
I don't think storing <k, b> is a good idea, because k, as a float number is not a precise value. Do you got Accepted by using this method ?
Therefore, I used an O(n^3) algorithm, with dynamic programing which can decrease the average steps number to (n+1)*n*n/4
. (the running time in 44 ms)
For a line going through two points you can store the deltas in x and y as a representation for the slope of that line (so you have a pair of values per line). To check that two lines (p,q)
and (s,t)
are parallel using this representation, use the predicate (p * t == q * s)
. But this does not tell us if they are the same line.
To check that they are the same line, we need a point in each of them. So instead of storing the deltas, we store the two points that the line goes through.
struct Line
{ Point p, q; };
Point sub(Point & p, Point & q)
{ Point s(p.x - q.x, p.y - q.y);
return s;
}
int dot(Point p, Point q)
{ return (p.x * q.x + p.y * q.y);
}
bool sameLine(Line & L1, Line & L2)
{ int dx1 = abs(L1.p.x - L1.q.x);
int dy1 = abs(L1.p.y - L1.q.y);
int dx2 = abs(L2.p.x - L2.q.x);
int dy2 = abs(L2.p.y - L2.q.y);
if(dx1 * dy2 != dx2 * dy1) return false;
/* At this point, L1 and L2 must be parallel. Are they the same?
*/
Point p, q;
p = sub(L2.p, L1.q);
q = sub(L2.q, L1.q);
return (dot(p, q) == 0);
}
This solution does not use gcd
's so it's faster (maybe). It's also accurate.
Inspired by @porker2008, For each point P, we tried to find the line with most points AND containing P. So calculating the slope is enough. It maybe hard to be faster than O(n^2).
int gcd(int a, int b){
return a?a/abs(a)*abs(gcd(b%a, a)):b;
}
int maxPoints(vector<Point> &points) {
int result=0;
for(int i=0;i<points.size();i++){
unordered_map<string,int> count;
int same=1,mx=0;
for(int j=i+1;j<points.size();j++){
int x=points[i].x-points[j].x;
int y=points[i].y-points[j].y;
int g=gcd(x,y);
if(!g){same++;continue;}
x/=g,y/=g;
mx=max(mx,++count[to_string(x)+" "+to_string(y)]);
}
result=max(result,mx+same);
}
return result;
}