Anyone could find out the bugs in this algorithm please ? Help ! crazing for the result of OJ is WA . T__T


  • 2
    P

    My algorithm is below , I think its thought is simple , it depends on :

    When 2 vector (v1(x1,y1) , v2(x2,y2) ) is parallel , x1/x2 === y1/y2 => x1y2 === y1x2 .

    so , I list all vectors with given points , if a point (p(x0,y0)) is on a line (decided by p1(x1,y1),p2(x2,y2) , vector is v(x2-x1,y2-y1)) , the point and one end point (such as p1) of the line will make up a vector v0(x0-x1,y0-y1) , v0 is parallel with v1 .
    so , (x0 - x1) * (y2 - y1) === (y0 - y1)*(x2 - x1 ) , so the set of v will add one point p
    I just count points of all vector set and select max points num .


    but in one case input is :

    [(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)]

    my result is

    19

    and the answer is

    12


    I cant find the error or bug in my program , any can help me ? Thanks a billion !


    class Solution {
        		public:
        			int maxPoints(vector<Point> &points) {
        				//find them on a same line
        				if(points.size() <= 2)
        				{
        					return points.size();	
        				}
        				std::vector<std::pair<Point,int> >	mp;
        				int maxn = 2;
        				for(int i = 0;i < points.size(); ++i)
        				{
        
        					mp.clear();
        					for(int j = i+1; j < points.size(); ++j)
        					{
        						Point pt(points[j].x-points[i].x , points[j].y - points[i].y);
        						std::vector<std::pair<Point,int> >::iterator it = mp.begin();
        						bool bFind = false;
        						while(it != mp.end())
        						{
        							if(pt.x*(it->first.y) == pt.y*(it->first.x))
        							{   
        								it->second++;	
        								if(maxn < it->second)
        								{
        									maxn = it->second;
        								}
        								bFind = true;
        							}
        							it++;	
        						}
        						if(false == bFind)
        						{
        							mp.push_back(std::make_pair(pt,2));
        						}
        					}
        				}
        				return maxn;
        			}
        	};

  • 1
    Y

    Your vector v(x,y) collects all line segments with slope y/x. But those segments are not necessarily in the same line, as a line is decided by its slope and y-intersect.

    You can use v( (y1-y2)/(x1-x2) , (x1y2-x2y1)/(x1-x2) ) to represent the line. That should give you the right answer. Another solution is to use Ax+By+C=0 to represent the line. Each point (x0,y0) that satisfies Ax0+By0+C=0 is in this line.


  • 0
    P

    Yeap ! you are great ! thanks a billion !!


  • 0
    P

    In fact , the alogrithm collects all line , but a bug in it .
    the bug is when two points (points[i],points[j]) is same , it will generate a line that past points[i] and slope = INF (0,0) .
    and this line parallel with any vector (points[i],points[k]) , so if meet this , the algorithm is invalid . just except this case will be right .
    in the sample case ,
    (115,359),(115,359) is same ,


  • 0
    P

    Collecting all line that past p[i] and slope is (p[i]->p[j]) .
    Should be carefully dealing with the slope is 0 .


  • 0
    Y

    Thanks for your update! I forgot to mention that additional effort is needed for handling duplicate points and vertical lines (whose slope is INF).


Log in to reply
 

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