Number of triangles that can be formed with given N points | Python3 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
from collections import defaultdict NEW_LINE from math import gcd NEW_LINE def countTriangles ( P , N ) : NEW_LINE INDENT mp = defaultdict ( lambda : 0 ) NEW_LINE ans = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT mp . clear ( ) NEW_LINE for j in range ( i + 1 , N ) : NEW_LINE INDENT X = P [ i ] [ 0 ] - P [ j ] [ 0 ] NEW_LINE Y = P [ i ] [ 1 ] - P [ j ] [ 1 ] NEW_LINE g = gcd ( X , Y ) NEW_LINE X //= g NEW_LINE Y //= g NEW_LINE mp [ ( X , Y ) ] += 1 NEW_LINE DEDENT num = N - ( i + 1 ) NEW_LINE ans += ( num * ( num - 1 ) ) // 2 NEW_LINE for j in mp : NEW_LINE INDENT ans -= ( mp [ j ] * ( mp [ j ] - 1 ) ) // 2 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT P = [ [ 0 , 0 ] , [ 2 , 0 ] , [ 1 , 1 ] , [ 2 , 2 ] ] NEW_LINE N = len ( P ) NEW_LINE print ( countTriangles ( P , N ) ) NEW_LINE DEDENT