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

A geometrical problem - Need help
Автор Rupai, 14 лет назад, По-английски
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.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
For the first problem. Choose a point A, then sort all other points Pi by an angle formed by a line APi and coordinate axes. Then you can test all lines going through A and including at least two of points of the entire given set in linear time, and a whole time complexity for this part of a problem is O(N2logN).
But what is a "1/4 shape" parabola?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Actually 1/4 shape parabola means this type of shape I try to draw here.
                             .
                         .
                      .
                   .
                .
             .
           .
          .
         .
        .
       .
      .
     . 
    .
    .
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      I didn't get it. Surely, there is a definition of this term in the problem statement. Just retell it.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Actually this problem is mine. It's not from any site. Would you please visit this site http://en.wikipedia.org/wiki/Parabola. Here the first picture is "A parabola". In my problem I don't want to draw the full parabola, I want just half of it. If you divide the picture in the middle then you find the shape that is I try to drawn in the above. Thank you for your reply. The solution of first part really help me.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Not at all, the first part is a very typical geometrical problem. But for the second part I can suggest only an O(N3logN) solution by analogy: fix two points, then sort other by something like an "angle in parabolical coordinates", i.e. by some coefficient in an equation of a parabola which is going to be drawn through the three. But if N is about 1000, it should be rather slow, of course.
          → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think, parabolic part can be solved in a similar way. First fix one point. Now for each second point you can "draw" a parabola or a line through them. Now you have a multiset of parabolas/lines and need to find the the one with the most occurences in it. Of such answers for each ("fixed") point choose maximal. O(N^2logN) complexity. Well, I assume the parabola has a form f(x)=(x-a)^2+b, i.e. has fixed x^2 coefficient.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Yeah, it seems that we can generalize this method to drawing any curve, and its time complexity should be O(NklogN), where k is a number of independent parameters in an equation of a curve :)
      → Ответить
14 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
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
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hi,

    Can I know how you solve the 2nd problem? I am not sure how you can use the hash table to solve it.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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)
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
        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.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
кстати, какого фига вы пишете в русском интерфейсе? уже 8 постов написали на своем ломаном английском.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ы. Это не "вы", это, походу, я один виноват - там ведь в ответе на коммент уже нельзя язык менять. Да, тупим, тупим... Ну ладно хоть топикстартер уже, видимо, привык к безалаберным русским - читает нормально и даже не возмущается =)
    → Ответить