# Number of triangles that can be formed with given N points

Given X and Y coordinates of N points on a Cartesian plane. The task is to find the number of possible triangles with the non-zero area that can be formed by joining each point to every other point.

**Examples:**

Input: P[] = {{0, 0}, {2, 0}, {1, 1}, {2, 2}}Output: 3 Possible triangles can be [(0, 0}, (2, 0), (1, 1)], [(0, 0), (2, 0), (2, 2)] and [(1, 1), (2, 2), (2, 0)]Input: P[] = {{0, 0}, {2, 0}, {1, 1}}Output: 1

A **Naive approach** has been already discussed in Number of possible Triangles in a Cartesian coordinate system

**Efficient Approach**: Consider a point Z and find its slope with every other point. Now, if two points are having the same slope with point Z that means the 3 points are collinear and they cannot form a triangle. Hence, the number of triangles having Z as one of its points is the number of ways of choosing 2 points from the remaining points and then subtracting the number of ways of choosing 2 points from points having the same slope with Z. Since Z can be any point among N points, we have to iterate one more loop.

Below is the implementation of above approach:

## C++

`// C++ implementation of the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// This function returns the required number` `// of triangles` `int` `countTriangles(pair<` `int` `, ` `int` `> P[], ` `int` `N)` `{` ` ` `// Hash Map to store the frequency of` ` ` `// slope corresponding to a point (X, Y)` ` ` `map<pair<` `int` `, ` `int` `>, ` `int` `> mp;` ` ` `int` `ans = 0;` ` ` ` ` `// Iterate over all possible points` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `mp.clear();` ` ` ` ` `// Calculate slope of all elements` ` ` `// with current element` ` ` `for` `(` `int` `j = i + 1; j < N; j++) {` ` ` `int` `X = P[i].first - P[j].first;` ` ` `int` `Y = P[i].second - P[j].second;` ` ` ` ` `// find the slope with reduced` ` ` `// fraction` ` ` `int` `g = __gcd(X, Y);` ` ` `X /= g;` ` ` `Y /= g;` ` ` `mp[{ X, Y }]++;` ` ` `}` ` ` `int` `num = N - (i + 1);` ` ` ` ` `// Total number of ways to form a triangle` ` ` `// having one point as current element` ` ` `ans += (num * (num - 1)) / 2;` ` ` ` ` `// Subtracting the total number of ways to` ` ` `// form a triangle having the same slope or are` ` ` `// collinear` ` ` `for` `(` `auto` `j : mp)` ` ` `ans -= (j.second * (j.second - 1)) / 2;` ` ` `}` ` ` `return` `ans;` `}` ` ` `// Driver Code to test above function` `int` `main()` `{` ` ` `pair<` `int` `, ` `int` `> P[] = { { 0, 0 }, { 2, 0 }, { 1, 1 }, { 2, 2 } };` ` ` `int` `N = ` `sizeof` `(P) / ` `sizeof` `(P[0]);` ` ` `cout << countTriangles(P, N) << endl;` ` ` `return` `0;` `}` |

## Python3

`# Python3 implementation of the above approach ` `from` `collections ` `import` `defaultdict` `from` `math ` `import` `gcd` ` ` `# This function returns the ` `# required number of triangles ` `def` `countTriangles(P, N): ` ` ` ` ` `# Hash Map to store the frequency of ` ` ` `# slope corresponding to a point (X, Y) ` ` ` `mp ` `=` `defaultdict(` `lambda` `:` `0` `) ` ` ` `ans ` `=` `0` ` ` ` ` `# Iterate over all possible points ` ` ` `for` `i ` `in` `range` `(` `0` `, N): ` ` ` `mp.clear() ` ` ` ` ` `# Calculate slope of all elements ` ` ` `# with current element ` ` ` `for` `j ` `in` `range` `(i ` `+` `1` `, N): ` ` ` `X ` `=` `P[i][` `0` `] ` `-` `P[j][` `0` `] ` ` ` `Y ` `=` `P[i][` `1` `] ` `-` `P[j][` `1` `] ` ` ` ` ` `# find the slope with reduced ` ` ` `# fraction ` ` ` `g ` `=` `gcd(X, Y) ` ` ` `X ` `/` `/` `=` `g ` ` ` `Y ` `/` `/` `=` `g ` ` ` `mp[(X, Y)] ` `+` `=` `1` ` ` ` ` `num ` `=` `N ` `-` `(i ` `+` `1` `) ` ` ` ` ` `# Total number of ways to form a triangle ` ` ` `# having one point as current element ` ` ` `ans ` `+` `=` `(num ` `*` `(num ` `-` `1` `)) ` `/` `/` `2` ` ` ` ` `# Subtracting the total number of ` ` ` `# ways to form a triangle having ` ` ` `# the same slope or are collinear ` ` ` `for` `j ` `in` `mp: ` ` ` `ans ` `-` `=` `(mp[j] ` `*` `(mp[j] ` `-` `1` `)) ` `/` `/` `2` ` ` ` ` `return` `ans ` ` ` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` ` ` `P ` `=` `[[` `0` `, ` `0` `], [` `2` `, ` `0` `], [` `1` `, ` `1` `], [` `2` `, ` `2` `]] ` ` ` `N ` `=` `len` `(P) ` ` ` `print` `(countTriangles(P, N))` ` ` `# This code is contributed by Rituraj Jain` |

**Output:**

3