Número de triángulos que se pueden formar con N puntos dados

Dadas las coordenadas X e Y de N puntos en un plano cartesiano. La tarea es encontrar el número de triángulos posibles con el área distinta de cero que se pueden formar al unir cada punto con todos los demás puntos. Ejemplos:

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

Ya se ha discutido un enfoque ingenuo en Número de triángulos posibles en un sistema de coordenadas cartesianas. Enfoque eficiente : Considere un punto Z y encuentre su pendiente con cualquier otro punto. Ahora, si dos puntos tienen la misma pendiente con el punto Z, eso significa que los 3 puntos son colineales y no pueden formar un triángulo. Por lo tanto, el número de triángulos que tienen a Z como uno de sus puntos es el número de formas de elegir 2 puntos de los puntos restantes y luego restar el número de formas de elegir 2 puntos de los puntos que tienen la misma pendiente con Z. Dado que Z puede ser cualquier punto entre N puntos, tenemos que iterar un bucle más. A continuación se muestra la implementación del enfoque anterior: 

// 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 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

// 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 triangles
function 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 function
let 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

3

Complejidad temporal: O(N ² logN)

Espacio Auxiliar: O(N)