# Any better solution than O(n^2) ?

• 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:

1. not all lines could be represented by y = kx + b, e.g. x = 1, so what line representation should we use?
2. how to write c++ code to store <k,b> in a hashset. So exactly what STL container should we use to hash a pair of double value?

Thanks a lot!

• Storing `<k,b>` is not a good idea.

Avoid using `y = kx + b`.

Try using `ax + by + c = 0`.

I don't know if there is some algorithm running faster than O(N^2). I will be glad to know if someone else does.

• to use hashset, use `unordered_set`; to use hashmap, use `unordered_map`. In this case, you may have to define a class that do the hash

• I converted <k, b> into String by Double.toString(k) + Double.toString(b) (in Java).

• how do you deal with the case where `<k, b>` does not exist

• ax + by + c = 0 does look good, but how do you calculate <a,b,c> by only two points? Given (x1,y1) and (x2,y2), there is no unique solution for <a,b,c>.
Still I hate using double too...

• convert whatever <k,b> or <a,b,c> to string for hashing is a smart idea! @tuliren

• Because it is string, you can save whatever cases you want. When k does not exist, just store the string "b=..." into the HashSet.

• I guess we have to calculate the `gcd` of `a` and `b`, and then do `a = a / gcd; b = b / gcd;`.

• for two points `(x0, y0)` and `(x1, y1)` where `x0 != x1` or `y0 != y1`, we can set `a = y1 - y0`, `b = x0 - x1` and `c = x1 * y0 - x0 * y1`. Then calculate the `gcd` of `a`, `b` and `c` and divide them by `gcd`. Then make `a` becomes non-negative and `b` non-negative when `a` is zero

• Awesome! @porker2008

• Hi Porker, your solution is good. But do we have to find gcd? The only reason to use ax+by+c=0 is to cover the case where b=0.
When b==0, we always set a=1. When b!=0, we always unify b=1. Then given each possible in 2D map, there is only one unique set of (a,b,c).

• You are right, when `b` is `0`, `a` is always `1`; but when `b` is not `0`, we don't always unify `b` to `1` because `a`, `b`, `c`, must be integers.

• Thanks Porker, I did not notice that you are trying to find the integers for <a,b,c>. GCD will make the solution more accurate but it takes higher running time. Is there an efficient way to calculate the GCD for three integers? Appreciate for your sharing.

• 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)

• how do you handle duplicated points? I cannot figure out a way to handle duplicated points with O(n^2).

• Actually, you can reconstruct a new points set as <Point, count> by using unordered_map, which can be done in O(n)

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.