introart's blog

[Solved] Need help in Geometry problem
By introart, history, 3 years ago, In English

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:

Can anyone please look into this matter? That would be a great help.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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 line x=?. 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 and b 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>>, where ll denotes long long and ii denotes pair<ll,ll>. The key of the map would store a pair of k and b and the value of the map would store a set of indices for points that lie on y=kx+b.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply