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
7Efficient 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.
Steps to solve the problem:
- Initialize an empty map mp and a variable ans to 0.
- Iterate from 0 to N-1.
- Clear the map mp.
- For each point i, calculate the slope of all other points with respect to the current point.
- calculate the greatest common divisor (GCD) of the difference in X and Y coordinate
- between point i and j. Divide the difference in X and Y coordinates by their GCD.
- Store the slope as a key-value pair in the map mp, where the key is a pair of integers representing the slope and the value is the frequency of that slope.
- Calculate the number of ways by the formula (N – (i + 1)) * (N – (i + 1) – 1) / 2. Add this value to the and.
- Iterate over the map mp, and for each key-value pair, calculate the number of ways by the formula j.second * (j.second – 1) /2.
- Subtract this value from the and.
- Return the final value of ans.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// This function returns the required number// of trianglesint 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 functionint 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;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG { // A recursive function to find gcd of two numbers. static int __gcd(int x, int y) { x = Math.abs(x); y = Math.abs(y); while (y > 0) { int t = y; y = x % y; x = t; } return x; } // This function returns the required number // of triangles static int countTriangles(int[][] P, int N) { // Hash Map to store the frequency of // slope corresponding to a point (X, Y) // map<pair<int, int>, int> mp; HashMap<String, Integer> mp = new HashMap<String, Integer>(); 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][0] - P[j][0]; int Y = P[i][1] - P[j][1]; // find the slope with reduced // fraction int g = __gcd(X, Y); X = (int)(X / g); Y = (int)(Y / g); String key = String.valueOf(X) + "," + String.valueOf(Y); if (!mp.containsKey(key)) mp.put(key, 0); mp.put(key, mp.get(key) + 1); } int num = N - (i + 1); // Total number of ways to form a triangle // having one point as current element ans += (int)((num * (num - 1)) / 2); // Subtracting the total number of ways to // form a triangle having the same slope or are // collinear for (Map.Entry<String, Integer> entry : mp.entrySet()) ans -= (entry.getValue() * (entry.getValue() - 1)) / 2; } return ans; } // Driver Code to test above function public static void main(String[] args) { int[][] P = { { 0, 0 }, { 2, 0 }, { 1, 1 }, { 2, 2 } }; int N = P.length; System.out.println(countTriangles(P, N)); }}// The code is contributed by phasing17 |
Python3
# Python3 implementation of the above approach from collections import defaultdictfrom 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 Codeif __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 |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG { // A recursive function to find gcd of two numbers. static int __gcd(int x, int y) { x = Math.Abs(x); y = Math.Abs(y); while (y > 0) { int t = y; y = x % y; x = t; } return x; } // This function returns the required number // of triangles static int countTriangles(int[, ] P, int N) { // Hash Map to store the frequency of // slope corresponding to a point (X, Y) // map<pair<int, int>, int> mp; Dictionary<string, int> mp = new Dictionary<string, int>(); 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, 0] - P[j, 0]; int Y = P[i, 1] - P[j, 1]; // find the slope with reduced // fraction int g = __gcd(X, Y); X = (int)(X / g); Y = (int)(Y / g); int[] l1 = { X, Y }; string key = string.Join(", ", l1); if (!mp.ContainsKey(key)) mp[key] = 0; mp[key]++; } int num = N - (i + 1); // Total number of ways to form a triangle // having one point as current element ans += (int)((num * (num - 1)) / 2); // Subtracting the total number of ways to // form a triangle having the same slope or are // collinear foreach(var entry in mp) ans -= (entry.Value * (entry.Value - 1)) / 2; } return ans; } // Driver Code to test above function public static void Main(string[] args) { int[, ] P = { { 0, 0 }, { 2, 0 }, { 1, 1 }, { 2, 2 } }; int N = P.GetLength(0); Console.WriteLine(countTriangles(P, N)); }}// The code is contributed by Nidhi goel |
Javascript
// JavaScript implementation of the above approach// A recursive function to find gcd of two numbers. function __gcd(x, y) { if ((typeof x !== 'number') || (typeof y !== 'number')) return false; x = Math.abs(x); y = Math.abs(y); while(y) { var t = y; y = x % y; x = t; } return x;}// This function returns the required number// of trianglesfunction countTriangles(P, N){ // Hash Map to store the frequency of // slope corresponding to a point (X, Y) // map<pair<int, int>, int> mp; let mp = new Map(); let ans = 0; // Iterate over all possible points for (let i = 0; i < N; i++) { mp.clear(); // Calculate slope of all elements // with current element for (let j = i + 1; j < N; j++) { let X = P[i][0] - P[j][0]; let Y = P[i][1] - P[j][1]; // find the slope with reduced // fraction let g = __gcd(X, Y); X = Math.floor(X/g); Y = Math.floor(Y/g); if(mp.has([X, Y].join())){ mp.set([X, Y].join(), mp.get([X, Y].join()) + 1); } else{ mp.set([X, Y].join(), 1); } } let num = N - (i + 1); // Total number of ways to form a triangle // having one point as current element ans += Math.floor((num * (num - 1)) / 2); // Subtracting the total number of ways to // form a triangle having the same slope or are // collinear for (const [key, value] of mp.entries()) ans -= (value * (value - 1)) / 2; } return ans;}// Driver Code to test above functionlet P = [[0, 0], [2, 0], [1, 1 ], [2, 2 ]];let N = P.length;console.log(countTriangles(P, N));// The code is contributed by Nidhi goel |
Output:
3
Time Complexity: O(N2logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
