Count number of triangles cut by the given horizontal and vertical line segments | C ++ program for the above approach ; Store the minimum and maximum X and Y coordinates ; Function to convert string to int ; Function to print the number of triangles cut by each line segment ; Initialize Structure ; Find maximum and minimum X and Y coordinates for each triangle ; Minimum X ; Maximum X ; Minimum Y ; Maximum Y ; Traverse each cut from 0 to M - 1 ; Store number of triangles cut ; Extract value from the line segment string ; If cut is made on X - axis ; Check for each triangle if x lies b / w max and min X coordinates ; If cut is made on Y - axis ; Check for each triangle if y lies b / w max and min Y coordinates ; Print answer for ith cut ; Driver Code ; Given coordinates of triangles ; Given cuts of lines ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Tri { int MinX , MaxX , MinY , MaxY ; } ; int StringtoInt ( string s ) { stringstream geek ( s ) ; int x ; geek >> x ; return x ; } int TriangleCuts ( vector < vector < int > > Triangle , string Cuts [ ] , int N , int M , int COL ) { Tri Minimized [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { int x1 = Triangle [ i ] [ 0 ] ; int y1 = Triangle [ i ] [ 1 ] ; int x2 = Triangle [ i ] [ 2 ] ; int y2 = Triangle [ i ] [ 3 ] ; int x3 = Triangle [ i ] [ 4 ] ; int y3 = Triangle [ i ] [ 5 ] ; Minimized [ i ] . MinX = min ( { x1 , x2 , x3 } ) ; Minimized [ i ] . MaxX = max ( { x1 , x2 , x3 } ) ; Minimized [ i ] . MinY = min ( { y1 , y2 , y3 } ) ; Minimized [ i ] . MaxY = max ( { y1 , y2 , y3 } ) ; } for ( int i = 0 ; i < M ; i ++ ) { string Cut = Cuts [ i ] ; int CutCount = 0 ; int CutVal = StringtoInt ( Cut . substr ( 2 , Cut . size ( ) ) ) ; if ( Cut [ 0 ] == ' X ' ) { for ( int j = 0 ; j < N ; j ++ ) { if ( ( Minimized [ j ] . MinX ) < ( CutVal ) & & ( Minimized [ j ] . MaxX ) > ( CutVal ) ) { CutCount ++ ; } } } else if ( Cut [ 0 ] == ' Y ' ) { for ( int j = 0 ; j < N ; j ++ ) { if ( ( Minimized [ j ] . MinY ) < ( CutVal ) & & ( Minimized [ j ] . MaxY ) > ( CutVal ) ) { CutCount ++ ; } } } cout << CutCount << " ▁ " ; } } int main ( ) { vector < vector < int > > Triangle = { { 0 , 2 , 2 , 9 , 8 , 5 } , { 5 , 0 , 6 , 3 , 7 , 0 } } ; int N = Triangle . size ( ) ; int COL = 6 ; string Cuts [ ] = { " X = 2" , " Y = 2" , " Y = 9" } ; int M = sizeof ( Cuts ) / sizeof ( Cuts [ 0 ] ) ; TriangleCuts ( Triangle , Cuts , N , M , COL ) ; return 0 ; }