A O(n^2) solution in CPP


  • -2
    L
    int maxPoints(vector<Point> &points) 
    {
    	int i, j;
    	double alpha;
    	int max=0;
    	int num;
    	int overlap;
    	if (points.size()<2)return points.size();
    	map<double, int>temp;
    	for (i = 0; i != points.size()-1; i++)
    	{
    		overlap = 0;
    		num = 1;
    		for (j = i + 1; j != points.size(); j++)
    		{
    			if (points[j].x == points[i].x && points[j].y == points[i].y) 
                {
    				overlap++;
    			}
    			else
    			{
    				alpha = atan2((points[j].y - points[i].y), (points[j].x - points[i].x));
    				if (alpha <= 0)alpha = atan2((points[i].y - points[j].y), (points[i].x - points[j].x));
    				temp[alpha]++;
    				num = temp[alpha]+1>num ? temp[alpha]+1 : num;
    			}
    		}
    		if (overlap > 0)num += overlap;
    		if (num > max)max = num;
    		temp.clear();
    	}
    	return max;
    }

Log in to reply
 

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