Count of intersections of M line segments with N vertical lines in XY plane | Function to create prefix sum array ; Initialize the prefix array to remove garbage values ; Marking the occurances of vertical lines ; Creating the prefix array ; Function that 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 vertical line  then it just touches it and  not intersects. ; We have assumed that x1 will be left and x2 right but if not then just swap ; Number of vertical lines ; Number of line segments ; Format : x1 , y1 , x2 , y2 ; First create the prefix array ; Print the total number of intersections
def createPrefixArray ( n , arr , prefSize , pref ) : NEW_LINE INDENT for i in range ( prefSize ) : NEW_LINE INDENT pref [ i ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT x = arr [ i ] + 1000000 NEW_LINE pref [ x ] += 1 NEW_LINE DEDENT for i in range ( 1 , prefSize ) : NEW_LINE INDENT pref [ i ] += pref [ i - 1 ] NEW_LINE DEDENT DEDENT def pointOfIntersection ( m , segments , size , pref ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( m ) : NEW_LINE INDENT x1 = segments [ i ] [ 0 ] NEW_LINE x2 = segments [ i ] [ 2 ] NEW_LINE x1 = x1 + 1000000 NEW_LINE x2 = x2 + 1000000 NEW_LINE if ( x1 != x2 ) : NEW_LINE INDENT if ( x1 > x2 ) : NEW_LINE INDENT x1 , x2 = x2 , x1 NEW_LINE DEDENT Occ_Till_Right = pref [ x2 - 1 ] NEW_LINE Occ_Till_Left = pref [ x1 ] NEW_LINE ans += ( Occ_Till_Right - Occ_Till_Left ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT N = 4 NEW_LINE M = 8 NEW_LINE size = 2000000 + 2 NEW_LINE pref = [ 0 ] * size NEW_LINE lines = [ - 5 , - 3 , 2 , 3 ] NEW_LINE segments = [ [ - 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 ] ] NEW_LINE createPrefixArray ( N , lines , size , pref ) NEW_LINE print ( pointOfIntersection ( M , segments , size , pref ) ) NEW_LINE