Wrong Answer on this one : [(0,9),(138,429),(115,359),(................]


  • 0
    H

    I got a fail respond on this one and I don't know why.
    Wrong Answer on this one : [(0,9),(138,429),(115,359),(115,359),(-30,-102),(230,709),(-150,-686),(-135,-613),(-60,-248),(-161,-481),(207,639),(23,79),(-230,-691),(-115,-341),(92,289),(60,336),(-105,-467),(135,701),(-90,-394),(-184,-551),(150,774)]

    Output: 11
    Expected: 12

    Here is the code:

    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            int point_num = points.size();
            int max_points = 0; //variable to store the max_points when traversing all the points
    	    for (int i = 0; i < point_num; ++i){ //i traverses all the points
    		    map<double, int> slope_map; //<slope, number>
    		    int duplicate = 0;
    		    for (int k = 0; k < point_num; ++k){ //k traverses all the other points to calculate all the slope the the point i
    			    if (k == i){ // if k traverses itself
    				    continue;
    			    }
    			    double slope = 0.0;
    			    if (points[k].x - points[i].x == 0){
    				    if (points[k].y - points[i].y == 0){
    					    ++duplicate;
    				    }
    				    else{
    					    slope = (double)INT_MAX;
    					    ++slope_map[slope];
    				    }
    			    }
    			    else{
    				    slope = (double)((points[k].y - points[i].y) / (points[k].x - points[i].x));
    				    ++slope_map[slope];
    			    }
    		    }
    		    max_points = duplicate + 1;
    		    for (map<double, int>::iterator it = slope_map.begin(); it != slope_map.end(); ++it){
    			    if (it->second + duplicate + 1> max_points){
    				    max_points = it->second + duplicate + 1;
    			    }
    		    }
    	    }
    	    return max_points;
        }
    };

  • 2
    M

    While you appear to have a one off error based off your answer, that is a coincidence. You have a pair of errors in your code.

    The first I found was:

       slope = (double)((points[k].y - points[i].y) / (points[k].x - points[i].x));
    

    You are storing the slope as a double, but not until after you've done integer division to get it, so every slope is currently a whole number. Switch to:

       slope = (double)(points[k].y - points[i].y) / (points[k].x - points[i].x);
    

    in order to get the slightly different slopes.

    Your second error was:

    max_points = duplicate + 1;
    

    This causes each round to completely overwrite the previous ones, and therefore is returning the max number of points on a line containing the final point. Remove this or add an overall recorder in addition to the current round-based one, and correct the slope calculation and it should be accepted.


Log in to reply
 

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