CODEWITHSUNDEEP
algorithm
Malice
Malice

Reputation: 1482

Finding all combinations of elements of a set satisfying a specific condition

Here's a problem i'm trying to solve : I'm given a set of lines having slope m and constant c. Now I need to find the number of intersection points of these lines that intersect on the right hand side of the y axis . This essentially implies that for lines 1 and 2

                    c1>c2 and m2>m1

I need an O(nlogn) algorithm that counts the total number of intersection points on the right hand side of y axis (if the algorithm exists) . I can always do the brute force to get an o(n2) algorithm , but i'm looking for a faster algorithm .

Upvotes: 2

Views: 337

Answers (3)

Sayalic
Sayalic

Reputation: 7650

Two sorted vectors will do that.

  1. Push all of the lines into vector v1.
  2. Sort v1 by constant c. After that, v1[0] is the line with smallest c.
  3. Traversal v1 from begin to end. For each element e in v1, we should only consider the element visited before(c1>c2). Now the task is to find among all of the visited element, the element with m2 > m1.
  4. So we just push the element which have been visited into a vector v2.We should keep it sorted by slope m after every insert(self-balance BST will do this task). Since v2 is sorted by m, a binary search will tell you how many element satisfy m2>m1.

Sort is n log n.

Insert to v2 is log n(It can be achieved with self-balance BST, and it will invoke n times).

Binary search is log n(invoke n times).

So it's O(nlog n)

If you write this in C++, it will be like that(I don't define v2, because you will implement a self-balance BST):

struct line
{
    int c,m;
    line(int a,int b):c(a),m(b){}
    bool operator <(const line &a) const
    {
        return m>a.m;
    }
};
bool cmp(const line &v1,const line &v2)
{
    return v1.c<v2.c;
}
int main()
{
    vector<line> v1;
    v1.push_back(line(1,3));
    v1.push_back(line(4,1));
    v1.push_back(line(3,1));
    v1.push_back(line(2,2));
    sort(v1.begin(),v1.end(),cmp);
    int ans=0;
    for(int i=0;i<v1.size();i++)
    {
        int num=v2.find(v1[i]);//return the number of element whose m is larger than  v1[i].
        ans+=num;
        v2.insert(v1[i]);// in every step, the element e in v2 will satisfy e.c<v1[i].c
    }
    cout << ans;
}

That's all. If you have any question, leave a comment to me.

Upvotes: 3

p1100i
p1100i

Reputation: 3740

I'm posting my solution because I think it's more simple to implement:

Let's say you got objects of Line and the following attributes are defined: 

- m (slope,    initialized on start)
- c (constant, initialized on start) 
- pos_m ( default 0 value )
- pos_c ( default 0 value )

Now, you have a V vector of these lines, then:

  1. Sort V by using key m on elements (O(nlogn)).
  2. Iterate V, on index i set V[i].pos_m = i (O(n)).
  3. Sort V by using key c on elements (O(nlogn)).
  4. Iterate V, on index i set V[i].pos_c = i. (O(n)).
  5. Let result = 0 now iterate on V index i do result += | V[i].pos_m - V[i].pos_c | (O(n))

On sorting, if the compared value is equal then use the other key for deciding the order ( if both are equal, they are the same line ). For example, if on 1. two lines got the same slope, then let the constant be the decider.

Upvotes: 0

Xantix
Xantix

Reputation: 3331

In the worst case, this problem is guaranteed to require O(n^2) operations.

Suppose I draw one line, then there can be no intersections. I can draw a line that intersects that line at a unique point. I can now draw a line that intersects both the preceding lines. I can continue drawing lines that intersect every previous line.

This means the number of intersection points could reach:

1 + 2 + 3 + 4 + 5 + ... + n-1

Given an input of size n lines, the size of the output to this problem could be (N*(N-1))/2 points or about N squared over 2.

Hence, even just outputting the correct answer requires O( n^2 ) in the worst case.

edited, ignore the previous, I thought you wanted the actual points of intersection, and not just the count.

Upvotes: -1

Related Questions