CODEWITHSUNDEEP
algorithmgeometry
Amit Srivastava
Amit Srivastava

Reputation: 11

Given N points with integers coordinates find the number of parallel lines

  1. nC2 will give the number of lines we can form in O(n^2) complexity.
  2. Finding the slope of these lines in O(n^2) complexity and store them in an array, say x.
  3. Sort x in O(n^2 logn) complexity.
  4. Search for the parallel lines in O(n^2) time.

Can we do better?

What if I have to find whether any two lines are parallel and that's it.Can we do that without finding all the lines?

Upvotes: 0

Views: 100

Answers (1)

user1196549
user1196549

Reputation:

As the coordinates are integer, you can use a hash table to store the N² slopes; represent them as irreducible fractions. This should limit the search for equal values to O(N²).

Upvotes: 1

Related Questions