Max Point On A Line different answers ON OJ and local machine(C++)


  • 0
    W

    Need help figuring out why my local machine returns 21 which is the expected answer, but OJ says my solution returns 22 for the following test:

    [(29,87),(145,227),(400,84),(800,179),(60,950),(560,122),(-6,5),(-87,-53),(-64,-118),(-204,-388),(720,160),(-232,-228),(-72,-135),(-102,-163),(-68,-88),(-116,-95),(-34,-13),(170,437),(40,103),(0,-38),(-10,-7),(-36,-114),(238,587),(-340,-140),(-7,2),(36,586),(60,950),(-42,-597),(-4,-6),(0,18),(36,586),(18,0),(-720,-182),(240,46),(5,-6),(261,367),(-203,-193),(240,46),(400,84),(72,114),(0,62),(-42,-597),(-170,-76),(-174,-158),(68,212),(-480,-125),(5,-6),(0,-38),(174,262),(34,137),(-232,-187),(-232,-228),(232,332),(-64,-118),(-240,-68),(272,662),(-40,-67),(203,158),(-203,-164),(272,662),(56,137),(4,-1),(-18,-233),(240,46),(-3,2),(640,141),(-480,-125),(-29,17),(-64,-118),(800,179),(-56,-101),(36,586),(-64,-118),(-87,-53),(-29,17),(320,65),(7,5),(40,103),(136,362),(-320,-87),(-5,5),(-340,-688),(-232,-228),(9,1),(-27,-95),(7,-5),(58,122),(48,120),(8,35),(-272,-538),(34,137),(-800,-201),(-68,-88),(29,87),(160,27),(72,171),(261,367),(-56,-101),(-9,-2),(0,52),(-6,-7),(170,437),(-261,-210),(-48,-84),(-63,-171),(-24,-33),(-68,-88),(-204,-388),(40,103),(34,137),(-204,-388),(-400,-106)]

    class Solution {
    
    	/*
    	A line can usually be represented as: y = a*x+b,
    	unless it's of the form x=constant.
    	In this case, line can be represented by this constant.
    	*/
    	struct Line
    	{
    		Line(float aa, float bb) :a(aa), b(bb){}
    		bool operator<(const Line& ll) const
    		{
    			return ((ll.a - a)>1e-6 || fabs(a - ll.a)<1e-7 && (ll.b - b)>1e-6);
    		}
    		float a, b;
    	};
    
    public:
    
    	int maxPoints(vector<Point> &points)
    	{
    		if (points.size() < 3)
    			return points.size();
    
    		size_t numPt = points.size();
    
    		vector<int> cnt(points.size(), 1);
    		for (size_t i = 0; i < numPt; i++)
    		for (size_t j = i + 1; j < numPt; j++)
    		{
    			int x1 = points[i].x, y1 = points[i].y;
    			int x2 = points[j].x, y2 = points[j].y;
    			if (x1 == x2 && y1 == y2)
    			{
    				cnt[i] ++;
    				cnt[j] --;
    			}
    		}
    
    		// With the help of cnt vector we now only
    		// compute lines for unique points
    		map< int, set<int> > mapA;
    		map< Line, set<int> > mapB;
    		for (size_t i = 0; i < numPt; i++)
    		{
    			if (cnt[i] == 0) continue;
    
    			for (size_t j = i + 1; j < numPt; j++)
    			{
    				if (cnt[j] == 0)    continue;
    
    				int x1 = points[i].x, y1 = points[i].y;
    				int x2 = points[j].x, y2 = points[j].y;
    				if (x1 == x2)
    				{
    					mapA[x1].insert(i);
    					mapA[x1].insert(j);
    				}
    				else
    				{
    					float a = float(y1 - y2) / float(x1 - x2);
    					float b = float(y1) - a*float(x1);
    					mapB[Line(a, b)].insert(i);
    					mapB[Line(a, b)].insert(j);
    				}
    			}
    		}
    
    		// whoever has the most elements in the set wins
    		int max = 0;
    		set<int>::iterator it;
    		map< int, set<int> >::iterator itA = mapA.begin();
    		while (itA != mapA.end())
    		{
    			int count = 0;
    			it = itA->second.begin();
    			while (it != itA->second.end())
    			{
    				count += cnt[*it];
    				it++;
    			}
    			if (max < count)
    				max = count;
    			itA++;
    		}
    
    		map< Line, set<int> >::iterator itB = mapB.begin();
    		while (itB != mapB.end())
    		{
    			int count = 0;
    			it = itB->second.begin();
    			while (it != itB->second.end())
    			{
    				count += cnt[*it];
    				it++;
    			}
    			if (max < count)
    				max = count;
    			itB++;
    		}
    
    		return max;
    	}
    };

  • 0
    R

    do not use div and float, that may be different in different machine


  • 0
    W

    Worked, thanks for the reminder!


Log in to reply
 

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