# Number of possible Triangles in a Cartesian coordinate system

Given n points in a Cartesian coordinate system. Count the number of triangles formed.

Examples:

```Input  : point[] = {(0, 0), (1, 1), (2, 0), (2, 2)
Output : 3
Three triangles can be formed from above points.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is to check if the determinant of the three points selected is non-zero or not. The following determinant gives the area of a Triangle (Also known as Cramer’s rule).

Area of the triangle with corners at (x1, y1), (x2, y2) and (x3, y3) is given by: We can solve this by taking all possible combination of 3 points and finding the determinant.

## C++

 `// C++ program to count number of triangles that can ` `// be formed with given points in 2D ` `#include ` `using` `namespace` `std; ` ` `  `// A point in 2D ` `struct` `Point ` `{ ` `   ``int` `x, y; ` `}; ` ` `  `// Returns determinant value of three points in 2D ` `int` `det(``int` `x1, ``int` `y1, ``int` `x2, ``int` `y2, ``int` `x3, ``int` `y3) ` `{ ` `   ``return` `x1*(y2 - y3) - y1*(x2 - x3) + 1*(x2*y3 - y2*x3); ` `} ` ` `  `// Returns count of possible triangles with given array ` `// of points in 2D. ` `int` `countPoints(Point arr[], ``int` `n) ` `{ ` `    ``int` `result = 0;  ``// Initialize result ` ` `  `    ``// Consider all triplets of points given in inputs ` `    ``// Increment the result when determinant of a triplet ` `    ``// is not 0. ` `    ``for` `(``int` `i=0; i

## Java

 `// Java program to count number  ` `// of triangles that can be formed  ` `// with given points in 2D ` ` `  `class` `GFG{ ` `// Returns determinant value  ` `// of three points in 2D ` `static` `int` `det(``int` `x1, ``int` `y1, ``int` `x2, ``int` `y2, ``int` `x3, ``int` `y3) ` `{ ` `    ``return` `(x1 * (y2 - y3) - y1 * ` `        ``(x2 - x3) + ``1` `* (x2 * ` `            ``y3 - y2 * x3)); ` `} ` ` `  `// Returns count of possible  ` `// triangles with given array ` `// of points in 2D. ` `static` `int` `countPoints(``int` `[][]Point, ``int` `n) ` `{ ` `    ``int` `result = ``0``; ``// Initialize result ` ` `  `    ``// Consider all triplets of  ` `    ``// points given in inputs ` `    ``// Increment the result when  ` `    ``// determinant of a triplet is not 0. ` `    ``for``(``int` `i = ``0``; i < n; i++) ` `        ``for``(``int` `j = i + ``1``; j < n; j++) ` `            ``for``(``int` `k = j + ``1``; k < n; k++) ` `                ``if``(det(Point[i][``0``], Point[i][``1``],  ` `                    ``Point[j][``0``], Point[j][``1``],  ` `                    ``Point[k][``0``], Point[k][``1``])>=``0``) ` `                    ``result = result + ``1``; ` ` `  `    ``return` `result; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args) ` `{ ` `int` `Point[][] = {{``0``, ``0``},{``1``, ``1``},{``2``, ``0``},{``2``, ``2``}}; ` `int` `n = Point.length; ` `System.out.println(countPoints(Point, n)); ` `} ` `} ` `// This code is contributed by ` `// mits `

## Python

 `# Python program to count number  ` `# of triangles that can be formed  ` `# with given points in 2D ` ` `  `# Returns determinant value  ` `# of three points in 2D ` `def` `det(x1, y1, x2, y2, x3, y3): ` `    ``return` `(x1 ``*` `(y2 ``-` `y3) ``-` `y1 ``*`  `            ``(x2 ``-` `x3) ``+` `1` `*` `(x2 ``*` `             ``y3 ``-` `y2 ``*` `x3)) ` ` `  `# Returns count of possible  ` `# triangles with given array ` `# of points in 2D. ` `def` `countPoints(Point, n): ` ` `  `    ``result ``=` `0` `# Initialize result ` ` `  `    ``# Consider all triplets of  ` `    ``# points given in inputs ` `    ``# Increment the result when  ` `    ``# determinant of a triplet is not 0. ` `    ``for` `i ``in` `range``(n): ` `        ``for` `j ``in` `range``(i ``+` `1``, n): ` `            ``for` `k ``in` `range``(j ``+` `1``, n): ` `                ``if``(det(Point[i][``0``], Point[i][``1``],  ` `                       ``Point[j][``0``], Point[j][``1``],  ` `                       ``Point[k][``0``], Point[k][``1``])): ` `                    ``result ``=` `result ``+` `1` ` `  `    ``return` `result ` ` `  `# Driver code ` `Point ``=` `[[``0``, ``0``], [``1``, ``1``],  ` `         ``[``2``, ``0``], [``2``, ``2``]] ` `n ``=` `len``(Point) ` `print``(countPoints(Point, n)) ` ` `  `# This code is contributed by ` `# Sanjit_Prasad `

## C#

 `// C# program to count number  ` `// of triangles that can be formed  ` `// with given points in 2D ` `using` `System; ` ` `  `class` `GFG{ ` `// Returns determinant value  ` `// of three points in 2D ` `static` `int` `det(``int` `x1, ``int` `y1, ``int` `x2, ``int` `y2, ``int` `x3, ``int` `y3) ` `{ ` `    ``return` `(x1 * (y2 - y3) - y1 * ` `        ``(x2 - x3) + 1 * (x2 * ` `            ``y3 - y2 * x3)); ` `} ` ` `  `// Returns count of possible  ` `// triangles with given array ` `// of points in 2D. ` `static` `int` `countPoints(``int``[,] Point, ``int` `n) ` `{ ` `    ``int` `result = 0; ``// Initialize result ` ` `  `    ``// Consider all triplets of  ` `    ``// points given in inputs ` `    ``// Increment the result when  ` `    ``// determinant of a triplet is not 0. ` `    ``for``(``int` `i = 0; i < n; i++) ` `        ``for``(``int` `j = i + 1; j < n; j++) ` `            ``for``(``int` `k = j + 1; k < n; k++) ` `                ``if``(det(Point[i,0], Point[i,1], Point[j,0], Point[j,1],Point[k,0], Point[k,1])>=0) ` `                    ``result = result + 1; ` ` `  `    ``return` `result; ` `} ` ` `  `// Driver code ` `public` `static` `void` `Main() ` `{ ` `int``[,] Point = ``new` `int``[,] { { 0, 0 }, { 1, 1 }, { 2, 0 }, { 2, 2 } }; ` `int` `n = Point.Length/Point.Rank; ` `Console.WriteLine(countPoints(Point, n)); ` `} ` `} ` `// This code is contributed by mits `

## PHP

 ` `

Output:

```3
```

Time Complexity: .

Optimization :
We can optimize the above solution to work in O(n2) using the fact that three points cannot form a triangle if they are collinear. We can use hashing to store slopes of all pairs and find all triangles in O(n2) time.

## tags:

Mathematical triangle Mathematical