Count number of intersections points for given lines between (i, 0) and (j, 1)
source link: https://www.geeksforgeeks.org/count-number-of-intersections-points-for-given-lines-between-i-0-and-j-1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Count number of intersections points for given lines between (i, 0) and (j, 1)
- Last Updated : 17 Nov, 2021
Given an array, lines[] of N pairs of the form (i, j) where (i, j) represents a line segment from coordinate (i, 0) to (j, 1), the task is to find the count of points of intersection of the given lines.
Example:
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.
In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.
Input: lines[] = {{1, 2}, {2, 1}}
Output: 1
Explanation: For the given two pairs, the line form (1, 0) to (2, 1) intersect with the line from (2, 0) to (1, 1) at point (1.5, 0.5). Hence the total count of points of intersection is 1.Input: lines[] = {{1, 5}, {2, 1}, {3, 7}, {4, 1}, {8, 2}}
Output: 5
Approach: The given problem can be solved using a Greedy approach using the policy-based data structure. It can be observed that for lines represented b two pairs (a, b) and (c, d) to intersect either (a > c and b < d) or (a < c and b > d) must hold true.
Therefore using this observation, the given array of pairs can be sorted in decreasing order of the 1stelement. While traversing the array, insert the value of the second element into the policy-based data structure and find the count of elements smaller than the second element of the inserted pair using the order_of_key function and maintain the sum of count in a variable. Similarly, calculate for the cases after sorting the given array of pairs in decreasing order of their 2nd element.
Below is the implementation of the above approach:
// C++ Program of the above appraoch#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>using namespace __gnu_pbds;using namespace std;// Defining Policy Based Data Strucuretypedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;// Function to count points// of intersection of pairs// (a, b) and (c, d)// such that a > c and b < dint cntIntersections(vector<pair<int, int> > lines,int N){// Stores the count// of intersection pointsint cnt = 0;// Initializing Ordered Multisetordered_multiset s;// Loop to iterate the arrayfor (int i = 0; i < N; i++) {// Add the count of integers// smaller than lines[i].second// in the total countcnt += s.order_of_key(lines[i].second);// Insert lines[i].second into ss.insert(lines[i].second);}// Return Countreturn cnt;}// Function to find the// total count of points of// intersections of all the given linesint cntAllIntersections(vector<pair<int, int> > lines,int N){// Sort the array in decreasing// order of 1st elementsort(lines.begin(), lines.end(),greater<pair<int, int> >());// Stores the total countint totalCnt = 0;// Function call for cases// with a > c and b < dtotalCnt += cntIntersections(lines, N);// Swap all the pairs of the array in order// to calculate cases with a < c and b > dfor (int i = 0; i < N; i++) {swap(lines[i].first, lines[i].second);}// Function call for cases// with a < c and b > dtotalCnt += cntIntersections(lines, N);// Return Answerreturn totalCnt;}// Driver Codeint main(){vector<pair<int, int> > lines{{1, 5}, {2, 1}, {3, 7}, {4, 1}, {8, 2}};cout << cntAllIntersections(lines,lines.size());return 0;}5
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK