Rupai's blog

A geometrical problem - Need help
By Rupai, 14 years ago, In English
My problem statement:

You are given N (N<=1000) points in X,Y co-ordinates. X and Y are both positive. Now, the problem is using maximum number of point you have to draw a straight line and also using maximum number of point you have to draw a 1/4 shape parabola. Actually, here you have to solve two problem at the same time. You can use any point to draw any one from those. You can use those point that are use to draw a straight line for 1/4 shape parabola.

Now all I need is your help to solve this problem. Please discuss your opinion.
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
we can use hash table to solve first problem with O(n^2), we don't need to sort points by angle, we can divide both coordinates by their gcd and add to hash table. and for second problem we also can use hash table to improve our solution in log(N) times
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hi,

    Can I know how you solve the 2nd problem? I am not sure how you can use the hash table to solve it.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    how to implement a hash table , I would rather use map of c++ stl .
    Although it increases the time complexity by lg(n).

    Plz Tell if its better to write a hash table implementation.
    (u can see i am a new)
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      we can use floating numbers to nomalize vector, 

      let's divide both coordinates by vector's length. we can hash doubles too

      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It takes O (log MaxX) to find gcd, so as I understand this solution is O (n^2 log MaxX).

    (And by the way it's not said that coordinates are integer.)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Hi,

      Can you please explain how you can use gcd to solve the problem? I am not sure how you can use that to solve either the quadratic or linear problem.
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 3   Vote: I like it +5 Vote: I do not like it
        I was talking only about straight lines.
        Three points A, B, C lie on the same line if and only if (B_x - A_x) / (B_y - A_y) = (C_x - A_x) / (C_y - A_y).
        (I don't want to talk about zeroes).

        So, we fix A, reduce all the fractions (B_x - A_x)/(B_y - A_y) (divide both parts by their gcd), count maximal number of equal pairs (we can use hash table here), and thus we get the maximal number of points that lie on one line incident to A.
        Check all points to find the answer.
        → Reply