Count Number of Intersection Points for Given Lines Between (i, 0) and (j, 1)

Brute Force Approach

The above problem can be solved straight away with a brute force algorithm. 

The algorithm is as follows:

• We can iterate through each line segment and write its linear equation
• For each line, we can iterate through all other lines and check if both the lines intersect
• We can write the explicit equations of all the line segments in the form of 

y = m * x + c

and check if any other line is intersecting it by solving both the linear equations

• We can declare a variable ‘COUNT’ to count the number of intersections and return the final answer

Complexity Analysis

Time Complexity: O(N²), where ‘N’ is the size of the array

Auxiliary Space: O(1), as no extra space is required

We can solve it with an approach better than O(N²). The intuition and the approach are discussed below. 

Intuition

Let us consider two line segments formed by pairs (a, b) and (c, d). So with observation, we can say that if both lines intersect at a point, then either of the below condition must hold:

• (a > c) and (b < d)  
• (a < c) and (b > d)

Diagram showing intersection of lines generated by the pairs (2, 3) and (3, 1)

The mentioned condition can be realized with the above example of intersecting lines generated by points (3, 0) and (1, 1); and (2, 0) and (3, 1), as

3 > 2 and 1 < 3 (First condition)

Approach

This problem can also be solved with a greedy approach with the help of Policy Based Data Structures with the least complexity. 

Policy-based data structures in C++ are somewhat similar to sets but have an edge over them. Apart from the standard library, they have some extra operations having a time complexity of O(log(n)). One of them is:

• order_of_key(K): Returns the number of elements strictly smaller than ‘K’.

Therefore from the above intuition, this problem can be solved in two parts. One part will be solved for the case (a > c) and (b < d) and another for (a < c) and (b > d). 

To calculate the first part, the array of pairs can be sorted in decreasing order of the first element. Then during traversal of the array, insert the value of the second element into the policy-based data structure. And finally, find the count of elements smaller than the second element of the inserted pair using the order of_key function and maintain the count of intersections in a variable. 

Similarly, to calculate the second part, sort the given array of pairs in decreasing order of their 2nd element or simply swap the first and second elements of all the pairs and traverse the array.

Program

// Program to find points of intersections.
#include <iostream> 
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// Defining Policy Based Data Structure.
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
        tree_order_statistics_node_update> multiset_ord;

// Function to count total points of intersection of lines.
int cntIntersections(vector<pair<int, int>> lines, int N)
{
      // Variable to store total points of intersection.
      int tot = 0;

      // Initializing Ordered Multisets to store pairs.
      multiset_ord pairs1, pairs2;

      // Sorting the array of pairs in decreasing order of first element.
      sort(lines.begin(), lines.end(), greater<pair<int, int> >());

      // Iterating the array for case when a > c and b < d.
      for (int i = 0; i < N; i++)
      {
            // Adding the count of integers smaller than lines[i].second in the total count.
            tot += pairs1.order_of_key(lines[i].second);

            // Insert lines[i].second into ordered multiset.
            pairs1.insert(lines[i].second);
      }

      // Iterating the array for case when a < c and b > d.
      for (int i = 0; i < N; i++)
      {
            // Adding the count of integers smaller than lines[i].first in the total count.
            tot += pairs2.order_of_key(lines[i].first);

            // Insert lines[i].first into ordered multiset.
            pairs2.insert(lines[i].first);
      }

      // Returning total number of intersections.
      return tot;
}

// Main Function.
int main()
{
      // Input for size of the array.
      int N;
      cin >> N;

      // Input for the vector of pairs representing lines.
      vector<pair<int, int> > lines(N);
      for (int i = 0; i < N; i++)
            cin >> lines[i].first >> lines[i].second;

      // Final Output.
      cout << "Total number of intersections are " << cntIntersections(lines, N);

      return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Example:

Input

4
1 2
2 3 
4 2 
2 4

Output

Total number of intersections are 2

Complexity Analysis

Time Complexity:

O(N * log(N)), where ‘N’ is the number of pairs.

Explanation: 

• The input of pairs into vectors took O(N) time.
• In function cntIntersections(), sorting of the vector took O(N * log(N)) of time.
• Traversal of vector and finding the number of intersections for the first condition took O(N * log(N)) time.
• Similarly, traversal of vector and finding the number of intersections for the second condition also took O(N * log(N)) time.

Hence, the most expensive operation for the above algorithm takes O(N * log(N)) of time.

Auxiliary Space:

O(N), where ‘N’ is the number of pairs.

Explanation: We have used the policy-based data structure to store all the N pairs, which occupy space of O(N).

Key Takeaways

Counting the number of intersection points for given lines between (i, 0) and (j, 1) is an interesting question, but it is not the only interesting question here. Find more interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practice, head over to our library section for many such interesting blogs. 

Check out the following problems - 

• Sum Of Two Arrays.
• Merge K Sorted Arrays.
• Intersection Of Two Arrays.
   

Keep learning.

Happy Coding!