2

I am given N lines, i.e, I am given a,b,c for N lines. And each line is of the form ax + by + c = 0. I need to find out the maximum number of lines that are parallel to each other.

For this, first I create a 2 dimensional array of the ratio A/B (-slope) and C/B (-intercept), except for b == 0 (for which I take slope as 1/eps , I have defined eps as a very small positive number).

Then I remove the duplicate entries in $O(n^2)$ complexity.

Again I do $O(N^2)$ scans to find how many lines for a given slope exist and report the maximum number.

It turns out that this a slower way of doing this. How can I make this faster ?

Also, I am writing my code in C++.

|improve this question
  • 2
    Code would help, we have no idea how you implemented the algorithm because we can't see it. – enderland Dec 5 '15 at 19:46
  • It sounds like you can just make an array of the slopes of the lines, and then this turns into the problem of finding the "mode" (most common number) in an array of floats. Once you know the word "mode", it's pretty easy to find decent algorithms for this. – Ixrec Dec 5 '15 at 19:48
  • why not sort them by a/b (or atan2(b,a) )and check how long the longest run of equal slopes is – ratchet freak Dec 5 '15 at 20:22
1

I would suggest creating a simple Slope object that simply contains a -A/B slope value.

Then for each line create a Slope object and save it to a Bag (counted set.)

Once you are done adding Slopes to the Bag, look for the Bag that contains the largest count. That's your largest number of parallel lines.

|improve this answer