Question: You are given a set of points and you have to find out the maximum points which lie on the same line.
Now this question is available on both Uva and Leetcode. But the same test case gives different outputs in different OJs.
Testcase:
- Test Case in Leetcode input format
- Test Case in Uva input format
According to the Leetcode: The answer is
5
- According to the test case on UDebug: The answer is
6
Can anyone please look into this matter? That would be a great help.
I haven't done research on whether the question and input really is the same in both cases, but I find that the Leetcode answer is the correct one when considering both the test case and the question from Leetcode.
To solve this problem one must find the maximum number of points that lie on a distinct linear function
y=kx+b
or a vertical linex=?
. Of course, there's no need to find all the lines that a points lies on. If the answer to the problem is larger than 1, we can process the points pairwise and find a common linear functions or vertical lines.Note that we should store both
k
andb
as fractions, i.e. pair of numerator and denominator, to avoid precision problems. These fractions must be reduced as much as possible... to do so divide both the numerator and denominator by the GCD and if the fraction is negative keep the sign on the numerator.To count how many points lie on a distinct linear function we can keep a
map<pair<ii, ii>, set<ll>>
, wherell
denoteslong long
andii
denotespair<ll,ll>
. The key of the map would store a pair ofk
andb
and the value of the map would store a set of indices for points that lie ony=kx+b
.Hey thanks a lot for your effort, I have followed the approach mentioned by you and got AC on Leetcode but the same code is giving the wrong answer verdict on Uva. Can you please take a look if these two questions are the same or not?
The questions are the same but the input actually isn't. If you took the input from UDebug there's actually a point
1 33
preceding the list you have copied.Thanks a lot! You are correct. There was a problem with my code in input parsing. The answer is 6. Thanks a lot. May God bless you with purple.