My Solution Without nested map in C++

• One key point is to convert the slope and intercept into a long long type.

`````` /*
*  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 (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) 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,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a

*  Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a

*  So we can use y0&x0 to track a line;

*  In my code, 'x' and 'y' stands for x0 and y0 mentioned above.

*  I convert them into a long long type for hash purpose.

*/

class Solution{
public:
int maxPoints(vector<Point> &points){
if (points.size()<=2) return points.size();

std::unordered_map<long long,int> map;
int result=0,localmax,overlap,x,y,gcd,curr;
long long key;

for (unsigned int i=0,size=points.size();i<size;i++){
if (result>=size-i) break;
map.clear();
localmax=0,overlap=0;
for (unsigned int j=i+1;j<size;j++){
x=points[j].x-points[i].x;
y=points[j].y-points[i].y;
//check overlap
if ((x==0)&&(y==0)){
overlap++;
continue;
}
gcd=generateGCD(x,y);
x/=gcd; y/=gcd;
//Calculate the key by shifting left 'x' 32 bits, and then add 'y'
key=0L;key+=x;key<<=32;key+=y;
//find x,then y;
int curr=++map[key];
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);

}
};``````

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