LeetCode Q149: Max Points on a Line (hard)

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

Using hash, for each point, check the number of all other points that are co-linear with current point. The problem will encounter is how to represent a line in hash map. Directly using float/double as slope will have precision problem. So, here I represent a slope using x and y, where x=p1.x-p0.x, y=p1.y-p0.y. Then to ensure uniqueness of each slope, x and y are divided by their GCD.

	/**
	* Definition for a point.
	* struct Point {
	* int x;
	* int y;
	* Point() : x(0), y(0) {}
	* Point(int a, int b) : x(a), y(b) {}
	* };
	*/
	class Solution {
	public:
	int GCD(int a, int b){
	if(b==0) return a;
	return GCD(b, a%b);
	}
	int maxPoints(vector<Point>& points) {
	if(points.size()<2)
	return points.size();
	int globalMax=0;
	for(int i=0; i<points.size(); i++){
	int overlap=1;
	int localMax=0;
	unordered_map<string, int> myMap;
	for(int j=i+1; j<points.size(); j++){
	if(points[i].x==points[j].x&&points[i].y==points[j].y){
	overlap++;
	continue;
	}
	int a=points[j].y-points[i].y;
	int b=points[j].x-points[i].x;
	int gcd=GCD(a, b);
	a=gcd!=0? a/gcd:a;
	b=gcd!=0? b/gcd:b;
	myMap[string(to_string(a)+"_"+to_string(b))]=myMap[string(to_string(a)+"_"+to_string(b))]+1;
	}
	for(auto it=myMap.begin(); it!=myMap.end(); it++)
	localMax=max(localMax, it->second);
	localMax+=overlap;
	globalMax=max(globalMax, localMax);
	}
	return globalMax;
	}
	};

view raw Q149MaxPointsOnaLine.cpp hosted with ❤ by GitHub