Dado un cuadrado con N puntos a cada lado del cuadrado y ninguno de estos puntos coincide con las esquinas del cuadrado. La tarea es calcular el número total de triángulos que se pueden formar usando estos 4 * N puntos (N puntos en cada lado del cuadrado) como vértices del triángulo.
Ejemplos:
Entrada: N = 1
Salida: 4
Hay un punto en cada lado. Entonces podemos hacer tres rectángulos dejando un punto y eligiendo otros tres puntos de los cuatro.
Entrada: N = 2
Salida: 56
Enfoque: El número de formas de elegir 3 puntos entre 4 * N puntos es (4 * N) C 3 . Sin embargo, algunos de ellos no forman un triángulo. Esto sucede cuando los tres puntos elegidos están en el mismo lado del cuadrado. La cuenta de estos tripletes es N C 3 para cada uno de los lados, es decir, 4 * N C 3 en total. Por lo tanto, el conteo requerido de triángulos será ( (4 * N) C 3 ) – (4 * N C 3 ) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of possible triangles int noOfTriangles(int n) { int y = 4 * n; return ((y * (y - 2) * (y - 1)) - (4 * n * (n - 2) * (n - 1))) / 6; } // Driver code int main() { int n = 1; cout << noOfTriangles(n); return 0; }
Java
// Java implementation of the above approach class GFG { // Function to return the count // of possible triangles static int noOfTriangles(int n) { int y = 4 * n; return ((y * (y - 2) * (y - 1)) - (4 * n * (n - 2) * (n - 1))) / 6; } // Driver code public static void main (String[] args) { int n = 1; System.out.println(noOfTriangles(n)); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the count # of possible triangles def noOfTriangles(n): y = 4 * n return ((y * (y - 2) * (y - 1)) - (4 * n * (n - 2) * (n - 1)))// 6 # Driver code n = 1 print(noOfTriangles(n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the above approach using System; class GFG { // Function to return the count // of possible triangles static int noOfTriangles(int n) { int y = 4 * n; return ((y * (y - 2) * (y - 1)) - (4 * n * (n - 2) * (n - 1))) / 6; } // Driver code public static void Main (String[] args) { int n = 1; Console.WriteLine(noOfTriangles(n)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // javascript implementation of the approach // Function to return the count // of possible triangles function noOfTriangles(n) { var y = 4 * n; return ((y * (y - 2) * (y - 1)) - (4 * n * (n - 2) * (n - 1))) / 6; } // Driver code var n = 1; document.write(noOfTriangles(n)); </script>
4
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)