Count of intersections of M line segments with N vertical lines in XY plane | Java 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
import java . util . * ; class GFG { static 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 ] ; } } static int pointsOfIntersection ( int m , int segments [ ] [ ] , 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 ) { int temp = x1 ; x1 = x2 ; x2 = temp ; } int Occ_Till_Right = pref [ x2 - 1 ] ; int Occ_Till_Left = pref [ x1 ] ; ans = ans + ( Occ_Till_Right - Occ_Till_Left ) ; } } return ans ; } public static void main ( String [ ] args ) { int N = 4 ; int M = 8 ; int size = 2000000 + 2 ; int [ ] pref = new int [ size ] ; int lines [ ] = { - 5 , - 3 , 2 , 3 } ; int 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 } } ; createPrefixArray ( N , lines , size , pref ) ; System . out . print ( pointsOfIntersection ( M , segments , size , pref ) + "NEW_LINE"); } }