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