A geometrical problem - Need help

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

Автор Rupai, 15 лет назад, По-английски

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.

geometry, parabola, straight line

Rupai
15 лет назад
18

Комментарии (18)

Написать комментарий?

Ferlon

15 лет назад, скрыть # |

For the first problem. Choose a point A, then sort all other points P_i by an angle formed by a line AP_i 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(N²logN).
But what is a "1/4 shape" parabola?

→ Ответить

Rupai

15 лет назад, скрыть # ^ |

Actually 1/4 shape parabola means this type of shape I try to draw here.

→ Ответить

Ferlon

15 лет назад, скрыть # ^ |

I didn't get it. Surely, there is a definition of this term in the problem statement. Just retell it.

→ Ответить

Rupai

15 лет назад, скрыть # ^ |

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.

→ Ответить

Ferlon

15 лет назад, скрыть # ^ |

Not at all, the first part is a very typical geometrical problem. But for the second part I can suggest only an O(N³logN) 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.

→ Ответить

al13n

15 лет назад, скрыть # ^ |

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.

→ Ответить

Ferlon

15 лет назад, скрыть # ^ |

Yeah, it seems that we can generalize this method to drawing any curve, and its time complexity should be O(N^klogN), where k is a number of independent parameters in an equation of a curve :)

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # |

← Rev. 3 →

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

→ Ответить

simp1eton

15 лет назад, скрыть # ^ |

Hi,

Can I know how you solve the 2nd problem? I am not sure how you can use the hash table to solve it.

→ Ответить

acc1	15 лет назад, скрыть # ^ \| 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) → Ответить

goo.gl_SsAhv

15 лет назад, скрыть # ^ |

← Rev. 2 →

we can use floating numbers to nomalize vector,

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

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # ^ |

or to put into hash table value (x / y) or (x * y^(-1) mod P)

→ Ответить

naagi

15 лет назад, скрыть # ^ |

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.)

→ Ответить

simp1eton

15 лет назад, скрыть # ^ |

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.

→ Ответить

naagi

15 лет назад, скрыть # ^ |

← Rev. 3 →

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.

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # |

кстати, какого фига вы пишете в русском интерфейсе? уже 8 постов написали на своем ломаном английском.

→ Ответить

Ferlon

15 лет назад, скрыть # ^ |

Ы. Это не "вы", это, походу, я один виноват - там ведь в ответе на коммент уже нельзя язык менять. Да, тупим, тупим... Ну ладно хоть топикстартер уже, видимо, привык к безалаберным русским - читает нормально и даже не возмущается =)

→ Ответить