C, 8ms, brute force


  • 0
    P
    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     * }
     */
    int maxPoints(struct Point* points, int pointsSize) {
        int i, j, k;
    	int maxpts = 0;
    	int n = 0, m;
    	struct Point v1, v2;
    	int dup;
    
    	for (i = 0; i < pointsSize; i++) {
    		dup = 0;
    		for (j = 0; j < pointsSize; j++) {
    		    if (j == i)
    		        continue;
    		    if (points[i].x == points[j].x
    		    && points[i].y == points[j].y)
    		        dup++;
    		}
    		n = dup + 1;
    		if (n > maxpts)
    			maxpts = n;
    		for (j = i + 1; j < pointsSize; j++) {
    			v1.x = points[i].x - points[j].x;
    			v1.y = points[i].y - points[j].y;
    			if (!v1.x && !v1.y)
    				continue;
    			m = 1;
    			for (k = j + 1; k < pointsSize; k++) {
    			   	v2.x = points[i].x - points[k].x;
    				v2.y = points[i].y - points[k].y;
    				if (!v2.x && !v2.y)
    				    continue;
    				if (v1.x * v2.y == v1.y * v2.x)
    					m++;
    			}
    			if (n + m > maxpts)
    			    maxpts = n + m;
    		}
    	}
    	return maxpts;
    }

Log in to reply
 

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