# Count number of triangles cut by the given horizontal and vertical line segments

Given an array **triangles[][]** consisting of **N **triangles of the form **{x1, y1, x2, y2, x3, y3}** and an array **cuts[]** consisting of **M** horizontal and vertical lines of the form **“X=x”** or **“Y=y”** which represents the equation of the line segments. The task is to print the number of triangles intersected by each cut in such a way that the left and the right parts of the triangle should have areas greater than zero.

**Examples:**

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:N = 2, triangles[][] = {{0, 2, 2, 9, 8, 5}, {5, 0, 6, 3, 7, 0}}, M = 3, cuts[] = {“X=2”, “Y=2”, “Y=9”}Output:1 1 0Explanation:

The cut at X = 2 divides the first triangle having vertices (0, 2), (2, 9) and (8, 5)

The cut at Y = 2 divides the second triangle having vertices (5, 0), (6, 3) and (7, 0)

The cut at Y = 9 divides none of the triangles.

Input:N = 2, triangles[][] = {{0, 2, 2, 9, 8, 5}}, M = 3, cuts[] = {“X=7”, “Y=7”, “X=9”}Output:1 1 0Explanation:

The cut at X = 2 divides the first triangle having vertices (0, 2), (2, 9) and (8, 5)

The cut at Y = 2 divides the second triangle having vertices (5, 0), (6, 3) and (7, 0)

The cut at Y = 9 divides none of the triangles.

**Approach:** Below is the conditions for a line segment to divide a triangle into two parts having non-zero areas:

- If a cut is made at
**X-axis**and it lies strictly in between the minimum and the maximum**X coordinate**of a triangle, then it divides the triangle in such a way that the left and the right parts should have areas greater than zero. - Similarly, If a cut is made at
**Y-axis**and it lies strictly in between the minimum and the maximum**Y coordinate**of a triangle, then it divides the triangle in such a way that the left and the right parts should have areas greater than zero.

Follow the steps below to solve the problem:

- Create a structure to store the maximum and minimum
**X**and**Y**coordinates for each triangle. - Traverse the array
**cuts[]**array over the range**[0, M – 1]**. - For each cut, initialize a counter
**count**with**0**to store the answer for the current cut and start traversing the**triangles[]**array from**j = 0 to N – 1**. - Check for each triangle,
**cuts[i]**is in the form**X=x**i.e., vertical cut and**x**strictly lies in between the maximum and the minimum**X**coordinate of**i**triangle, increment the counter^{th}**count**otherwise continue checking other triangles for each cut. - After calculating the answer for
**cuts[i]**, print**count**. - Repeat the steps above for each cut and print the count of triangle cut by each line.

Below is the implementation of the above approach:

## C++

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

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` `// Store the minimum and maximum` `// X and Y coordinates` `static` `class` `Tri` `{` ` ` `int` `MinX, MaxX, MinY, MaxY;` `};` `// Function to convert String to int` `static` `int` `StringtoInt(String s)` `{` ` ` `return` `Integer.valueOf(s);` `}` `static` `int` `min(` `int` `a, ` `int` `b, ` `int` `c)` `{` ` ` `return` `Math.min(a, Math.min(b, c));` `}` `static` `int` `max(` `int` `a, ` `int` `b, ` `int` `c)` `{` ` ` `return` `Math.max(a, Math.max(b, c));` `}` `// Function to print the number of` `// triangles cut by each line segment` `static` `void` `TriangleCuts(` `int` `[][] Triangle,` ` ` `String Cuts[], ` `int` `N, ` `int` `M, ` `int` `COL)` `{` ` ` ` ` `// Initialize Structure` ` ` `Tri []Minimized = ` `new` `Tri[N];` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++)` ` ` `{` ` ` `Minimized[i] = ` `new` `Tri();` ` ` `Minimized[i].MaxX = ` `0` `;` ` ` `Minimized[i].MaxY = ` `0` `;` ` ` `Minimized[i].MinX = ` `0` `;` ` ` `Minimized[i].MinY = ` `0` `;` ` ` `}` ` ` `// Find maximum and minimum X and Y` ` ` `// coordinates for each triangle` ` ` `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` `];` ` ` `// Minimum X` ` ` `Minimized[i].MinX = min(x1, x2, x3);` ` ` `// Maximum X` ` ` `Minimized[i].MaxX = max(x1, x2, x3);` ` ` `// Minimum Y` ` ` `Minimized[i].MinY = min(y1, y2, y3);` ` ` `// Maximum Y` ` ` `Minimized[i].MaxY = max(y1, y2, y3);` ` ` `}` ` ` `// Traverse each cut from 0 to M-1` ` ` `for` `(` `int` `i = ` `0` `; i < M; i++)` ` ` `{` ` ` `String Cut = Cuts[i];` ` ` ` ` `// Store number of triangles cut` ` ` `int` `CutCount = ` `0` `;` ` ` `// Extract value from the line` ` ` `// segment String` ` ` `int` `CutVal = StringtoInt(` ` ` `Cut.substring(` `2` `, Cut.length()));` ` ` `// If cut is made on X-axis` ` ` `if` `(Cut.charAt(` `0` `) == ` `'X'` `)` ` ` `{` ` ` ` ` `// Check for each triangle` ` ` `// if x lies b/w max and` ` ` `// min X coordinates` ` ` `for` `(` `int` `j = ` `0` `; j < N; j++)` ` ` `{` ` ` ` ` `if` `((Minimized[j].MinX) < (CutVal) &&` ` ` `(Minimized[j].MaxX) > (CutVal))` ` ` `{` ` ` `CutCount++;` ` ` `}` ` ` `}` ` ` `}` ` ` `// If cut is made on Y-axis` ` ` `else` `if` `(Cut.charAt(` `0` `) == ` `'Y'` `)` ` ` `{` ` ` ` ` `// Check for each triangle` ` ` `// if y lies b/w max and` ` ` `// min Y coordinates` ` ` `for` `(` `int` `j = ` `0` `; j < N; j++)` ` ` `{` ` ` `if` `((Minimized[j].MinY) < (CutVal) &&` ` ` `(Minimized[j].MaxY) > (CutVal))` ` ` `{` ` ` `CutCount++;` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Print answer for ith cut` ` ` `System.out.print(CutCount + ` `" "` `);` ` ` `}` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` ` ` `// Given coordinates of triangles` ` ` `int` `[][] Triangle = { { ` `0` `, ` `2` `, ` `2` `, ` `9` `, ` `8` `, ` `5` `},` ` ` `{ ` `5` `, ` `0` `, ` `6` `, ` `3` `, ` `7` `, ` `0` `} };` ` ` `int` `N = Triangle.length;` ` ` `int` `COL = ` `6` `;` ` ` `// Given cuts of lines` ` ` `String Cuts[] = { ` `"X=2"` `, ` `"Y=2"` `, ` `"Y=9"` `};` ` ` `int` `M = Cuts.length;` ` ` `// Function Call` ` ` `TriangleCuts(Triangle, Cuts,` ` ` `N, M, COL);` `}` `}` `// This code is contributed by Princi Singh` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Store the minimum and maximum` `// X and Y coordinates` `public` `class` `Tri` `{` ` ` `public` `int` `MinX, MaxX, MinY, MaxY;` `};` `// Function to convert String to int` `static` `int` `StringtoInt(String s)` `{` ` ` `return` `Int32.Parse(s);` `}` `static` `int` `min(` `int` `a, ` `int` `b, ` `int` `c)` `{` ` ` `return` `Math.Min(a, Math.Min(b, c));` `}` `static` `int` `max(` `int` `a, ` `int` `b, ` `int` `c)` `{` ` ` `return` `Math.Max(a, Math.Max(b, c));` `}` `// Function to print the number of` `// triangles cut by each line segment` `static` `void` `TriangleCuts(` `int` `[,] Triangle,` ` ` `String []Cuts,` ` ` `int` `N, ` `int` `M,` ` ` `int` `COL)` `{` ` ` ` ` `// Initialize Structure` ` ` `Tri []Minimized = ` `new` `Tri[N];` ` ` `for` `(` `int` `i = 0; i < N; i++)` ` ` `{` ` ` `Minimized[i] = ` `new` `Tri();` ` ` `Minimized[i].MaxX = 0;` ` ` `Minimized[i].MaxY = 0;` ` ` `Minimized[i].MinX = 0;` ` ` `Minimized[i].MinY = 0;` ` ` `}` ` ` `// Find maximum and minimum X and Y` ` ` `// coordinates for each triangle` ` ` `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];` ` ` `// Minimum X` ` ` `Minimized[i].MinX = min(x1, x2, x3);` ` ` `// Maximum X` ` ` `Minimized[i].MaxX = max(x1, x2, x3);` ` ` `// Minimum Y` ` ` `Minimized[i].MinY = min(y1, y2, y3);` ` ` `// Maximum Y` ` ` `Minimized[i].MaxY = max(y1, y2, y3);` ` ` `}` ` ` `// Traverse each cut from 0 to M-1` ` ` `for` `(` `int` `i = 0; i < M; i++)` ` ` `{` ` ` `String Cut = Cuts[i];` ` ` ` ` `// Store number of triangles cut` ` ` `int` `CutCount = 0;` ` ` `// Extract value from the line` ` ` `// segment String` ` ` `int` `CutVal = StringtoInt(` ` ` `Cut.Substring(2, Cut.Length - 2));` ` ` `// If cut is made on X-axis` ` ` `if` `(Cut[0] == ` `'X'` `)` ` ` `{` ` ` ` ` `// Check for each triangle` ` ` `// if x lies b/w max and` ` ` `// min X coordinates` ` ` `for` `(` `int` `j = 0; j < N; j++)` ` ` `{` ` ` `if` `((Minimized[j].MinX) < (CutVal) &&` ` ` `(Minimized[j].MaxX) > (CutVal))` ` ` `{` ` ` `CutCount++;` ` ` `}` ` ` `}` ` ` `}` ` ` `// If cut is made on Y-axis` ` ` `else` `if` `(Cut[0] == ` `'Y'` `)` ` ` `{` ` ` ` ` `// Check for each triangle` ` ` `// if y lies b/w max and` ` ` `// min Y coordinates` ` ` `for` `(` `int` `j = 0; j < N; j++)` ` ` `{` ` ` `if` `((Minimized[j].MinY) < (CutVal) &&` ` ` `(Minimized[j].MaxY) > (CutVal))` ` ` `{` ` ` `CutCount++;` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Print answer for ith cut` ` ` `Console.Write(CutCount + ` `" "` `);` ` ` `}` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` ` ` `// Given coordinates of triangles` ` ` `int` `[,] Triangle = { { 0, 2, 2, 9, 8, 5 },` ` ` `{ 5, 0, 6, 3, 7, 0 } };` ` ` `int` `N = Triangle.GetLength(0);` ` ` `int` `COL = 6;` ` ` `// Given cuts of lines` ` ` `String []Cuts = { ` `"X=2"` `, ` `"Y=2"` `, ` `"Y=9"` `};` ` ` `int` `M = Cuts.Length;` ` ` `// Function Call` ` ` `TriangleCuts(Triangle, Cuts,` ` ` `N, M, COL);` `}` `}` `// This code is contributed by Princi Singh` |

**Output:**

1 1 0

**Time Complexity:** O(M*N)**Auxiliary Space:** O(M+N)