Share an idea with you : )


  • 0
    E

    This idea comes from a homework from Coursera Algorithm Princeton.

    Basically, first calculate slops for a given point, then do a sort, and then find the maximum length with consecutive same value.

    Be careful with vertical lines and those points that are same with the given point.

    class Solution {
    public:
        int maxPoints(vector<Point>& points)
        {
        	int maxLength = 0;
        	for (int i = 0; i < points.size(); ++i)
        	{
        		std::vector<double> slops;
        		int same = 0;
        		int vertical = 0;
    
        		for (int j = 0; j < points.size(); ++j)
        		{
        			if (points[i].x == points[j].x && points[i].y == points[j].y)
        				same++;
        			else if (points[i].x == points[j].x)
        				vertical++;
    				else
        			{
        				double slop = (points[j].y - points[i].y) * 1.0 / (points[j].x - points[i].x);
        				slops.push_back(slop);
        			}
        		}
        		
        		sort(slops.begin(), slops.end());
        		
        		// normal points
        		int currentMax = 0;
        		int strike = slops.size() > 0 ? 1 : 0;
        		for (int i = 1; i < slops.size(); ++i)
        		{
        			if (slops[i] == slops[i - 1])
        				strike++;
        			else
        			{
        				currentMax = max(currentMax, strike);
        				strike = 1;
        			}
        		}
        		currentMax = max(currentMax, strike);
        		
        		// vertical points
        		currentMax = max(currentMax, vertical) + same;
    
                // max
        		maxLength = max(maxLength, currentMax);
        	}
    
        	return maxLength;
        }
    };

Log in to reply
 

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