Hay ‘n’ puntos en un plano, de los cuales ‘m’ puntos son colineales. ¿Encuentre el número de triángulos formados por los puntos como vértices?
Ejemplos:
Input : n = 5, m = 4 Output : 6 Out of five points, four points are collinear, we can make 6 triangles. We can choose any 2 points from 4 collinear points and use the single point as 3rd point. So total count is 4C2 = 6 Input : n = 10, m = 4 Output : 116
Número de triángulos = n C 3 – m C 3
¿Cómo funciona esta fórmula?
Considere el segundo ejemplo anterior. Hay 10 puntos, de los cuales 4 son colineales. Un triángulo estará formado por tres cualquiera de estos diez puntos. Por lo tanto, formar un triángulo equivale a seleccionar tres de los 10 puntos. Se pueden seleccionar tres puntos de los 10 puntos en n C 3 maneras.
Número de triángulos formados por 10 puntos cuando 3 de ellos no son colineales = 10 C 3 ……(i)
De manera similar, el número de triángulos formados por 4 puntos cuando 3 de ellos no son colineales = 4 C 3 …… ..(ii)
Dado que el triángulo formado por estos 4 puntos no es válido, el número requerido de triángulos formados = 10 C 3 – 4 C 3 = 120 – 4 = 116
C++
// CPP program to count number of triangles
// with n total points, out of which m are
// collinear.
#include <bits/stdc++.h>
using namespace std;
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
int nCk(int n, int k)
{
int C[k+1];
memset(C, 0, sizeof(C));
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++)
{
// Compute next row of pascal triangle
// using the previous row
for (int j = min(i, k); j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}
/* function to calculate number of triangle
can be formed */
int countTriangles(int n,int m)
{
return (nCk(n, 3) - nCk(m, 3));
}
/* driver function*/
int main()
{
int n = 5, m = 4;
cout << countTriangles(n, m);
return 0;
}
Java
//Java program to count number of triangles
// with n total points, out of which m are
// collinear.
import java.io.*;
import java.util.*;
class GFG {
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
static int nCk(int n, int k)
{
int[] C=new int[k+1];
for (int i=0;i<=k;i++)
C[i]=0;
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++)
{
// Compute next row of pascal triangle
// using the previous row
for (int j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}
/* function to calculate number of triangle
can be formed */
static int countTriangles(int n,int m)
{
return (nCk(n, 3) - nCk(m, 3));
}
public static void main (String[] args) {
int n = 5, m = 4;
System.out.println(countTriangles(n, m));
}
}
//This code is contributed by Gitanjali.
Python3
# python program to count number of triangles # with n total points, out of which m are # collinear. import math # Returns value of binomial coefficient # Code taken from https://goo.gl / vhy4jp def nCk(n, k): C = [0 for i in range(0, k + 2)] C[0] = 1; # nC0 is 1 for i in range(0, n + 1): # Compute next row of pascal triangle # using the previous row for j in range(min(i, k), 0, -1): C[j] = C[j] + C[j-1] return C[k] # function to calculate number of triangle # can be formed def countTriangles(n, m): return (nCk(n, 3) - nCk(m, 3)) # driver code n = 5 m = 4 print (countTriangles(n, m)) # This code is contributed by Gitanjali
C#
//C# program to count number of triangles
// with n total points, out of which m are
// collinear.
using System;
class GFG {
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
static int nCk(int n, int k)
{
int[] C=new int[k+1];
for (int i = 0; i <= k; i++)
C[i] = 0;
// nC0 is 1
C[0] = 1;
for (int i = 1; i <= n; i++)
{
// Compute next row of pascal triangle
// using the previous row
for (int j = Math.Min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
/* function to calculate number of triangle
can be formed */
static int countTriangles(int n,int m)
{
return (nCk(n, 3) - nCk(m, 3));
}
// Driver code
public static void Main ()
{
int n = 5, m = 4;
Console.WriteLine(countTriangles(n, m));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to count number
// of triangles with n total
// points, out of which m are collinear.
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
function nCk($n, $k)
{
for ($i = 0; $i <= $k; $i++)
$C[$i] = 0;
$C[0] = 1; // nC0 is 1
for ($i = 1; $i <= $n; $i++)
{
// Compute next row of pascal
// triangle using the previous row
for ($j = min($i, $k); $j > 0; $j--)
$C[$j] = $C[$j] + $C[$j - 1];
}
return $C[$k];
}
/* function to calculate number
of triangles that can be formed */
function countTriangles($n, $m)
{
return (nCk($n, 3) - nCk($m, 3));
}
// Driver Code
$n = 5;
$m = 4;
echo countTriangles($n, $m);
return 0;
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Javascript program to count number of triangles
// with n total points, out of which m are
// collinear.
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
function nCk(n, k)
{
let C = new Array(k+1);
C.fill(0);
C[0] = 1; // nC0 is 1
for (let i = 1; i <= n; i++)
{
// Compute next row of pascal triangle
// using the previous row
for (let j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}
/* function to calculate number of triangle
can be formed */
function countTriangles(n, m)
{
return (nCk(n, 3) - nCk(m, 3));
}
let n = 5, m = 4;
document.write(countTriangles(n, m));
// This code is contributed by divyesh072019.
</script>
Producción :
6