Count of intersections of M line segments with N vertical lines in XY plane | C ++ implementation for the above approach . ; Function to create prefix sum array ; Initialize the prefix array to remove garbage values ; Marking the occurences of vertical lines ; x is the value after Index mapping ; Creating the prefix array ; Function returns the count of total intersection ; ans is the number of points of intersection of the line segments with the vertical lines ; Index mapping ; We don 't consider a vertical  line segment because even if  it falls on a verticale line  then it just touches it and  not intersects. ; We have assumed that x1 will be left and x2 right but if not then we just swap them ; Driver code ; N is the number of vertical lines M is the number of line segments ; Format : x1 , y1 , x2 , y1 ; First create the prefix array ; Print the total number of intersections
#include <bits/stdc++.h> NEW_LINE using namespace std ; void createPrefixArray ( int n , int arr [ ] , int prefSize , int pref [ ] ) { for ( int i = 0 ; i < prefSize ; i ++ ) { pref [ i ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { int x = arr [ i ] + 1000000 ; pref [ x ] ++ ; } for ( int i = 1 ; i < prefSize ; i ++ ) { pref [ i ] += pref [ i - 1 ] ; } } int pointsOfIntersection ( int m , int segments [ ] [ 4 ] , int size , int pref [ ] ) { int ans = 0 ; for ( int i = 0 ; i < m ; i ++ ) { int x1 = segments [ i ] [ 0 ] ; int x2 = segments [ i ] [ 2 ] ; x1 = x1 + 1000000 ; x2 = x2 + 1000000 ; if ( x1 != x2 ) { if ( x1 > x2 ) { swap ( x1 , x2 ) ; } int Occ_Till_Right = pref [ x2 - 1 ] ; int Occ_Till_Left = pref [ x1 ] ; ans = ans + ( Occ_Till_Right - Occ_Till_Left ) ; } } return ans ; } int main ( ) { int N = 4 ; int M = 8 ; int size = 2000000 + 2 ; int pref [ size ] ; int lines [ N ] = { -5 , -3 , 2 , 3 } ; int segments [ M ] [ 4 ] = { { -2 , 5 , 5 , -6 } , { -5 , -2 , -3 , -5 } , { -2 , 3 , -6 , 1 } , { -1 , -3 , 4 , 2 } , { 2 , 5 , 2 , 1 } , { 4 , 5 , 4 , -5 } , { -2 , -4 , 5 , 3 } , { 1 , 2 , -2 , 1 } } ; createPrefixArray ( N , lines , size , pref ) ; cout << pointsOfIntersection ( M , segments , size , pref ) << endl ; return 0 ; }