When two line segments share exactly one common point, they are called the intersecting line segments. The intersecting line segments share a common point. And, this common point that exists on all intersecting line segments is called the point of intersection. Let us discuss a problem based on the point of intersection of two lines.

Problem Statement

An array containing ‘N’ pairs of the form (i, j), which represents a line segment from (i, 0) to (j, 1), is given. The task is to find the total number of points of intersections of lines formed with given coordinates.

Example:

Input: arr[] = {{4, 3}, {3, 4}}

Output: 1

Explanation: There will be only 1 point of intersection of lines generated between {4,0} and {3,1}, and {3, 0} and {4, 1}.

Between lines generated by the points (1, 0) and (2, 1), and (1, 0) and {3, 1}

Between lines generated by the points (1, 0) and (3, 1), and (4, 0) and (2, 1)

Between lines generated by the points (1, 0) and (3, 1), and (5, 0) and (1, 1)

Between lines generated by the points (1, 0) and (2, 1), and (4, 0) and (2, 1)

Between lines generated by the points (4, 0) and (2, 1), and (2, 0) and (4, 1)

Between lines generated by the points (4, 0) and (2, 1), and (5, 0) and (1, 1)

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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^{2}), 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^{2}). 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

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;
}

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.