Блог пользователя introart

Автор introart, история, 23 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
23 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        23 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.