Hay ‘n’ puntos en un plano de los cuales ‘m puntos son colineales. ¿Cuántas rectas diferentes se pueden formar?
Ejemplos:
Input : n = 3, m = 3 Output : 1 We can form only 1 distinct straight line using 3 collinear points Input : n = 10, m = 4 Output : 40
Número de rectas distintas = n C 2 – m C 2 + 1
¿Cómo funciona esta fórmula?
Considere el segundo ejemplo anterior. Hay 10 puntos, de los cuales 4 son colineales. Una línea recta estará formada por dos cualesquiera de estos diez puntos. Por lo tanto, formar una línea recta equivale a seleccionar dos de los 10 puntos. Se pueden seleccionar dos puntos de los 10 puntos en n C 2 maneras.
Número de rectas formadas por 10 puntos cuando 2 de ellos no son colineales = 10 C 2 …..…(i)
Análogamente, el número de rectas formadas por 4 puntos cuando 2 de ellos no son colineales = 4 C 2….(ii)
Dado que las líneas rectas formadas por estos 4 puntos son cuerdas, las líneas rectas formadas por ellos se reducirán a uno solo.
Número requerido de líneas rectas formadas = 10 C 2 – 4 C 2 + 1 = 45 – 6 + 1 = 40
La implementación del enfoque se da como:
C++
// CPP program to count number of straight lines
// 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 straight lines
can be formed */
int count_Straightlines(int n,int m)
{
return (nCk(n, 2) - nCk(m, 2)+1);
}
/* driver function*/
int main()
{
int n = 4, m = 3 ;
cout << count_Straightlines(n, m);
return 0;
}
Java
// Java program to count number of straight lines
// with n total points, out of which m are
// collinear.
import java.util.*;
import java.lang.*;
public class GfG {
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
public static int nCk(int n, int k)
{
int[] C = new int[k + 1];
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 straight lines
can be formed */
public static int count_Straightlines(int n, int m)
{
return (nCk(n, 2) - nCk(m, 2) + 1);
}
// Driver function
public static void main(String argc[])
{
int n = 4, m = 3;
System.out.println(count_Straightlines(n, m));
}
// This code is contributed by Sagar Shukla
}
Python
# Python program to count number of straight lines # with n total points, out of which m are # collinear. # Returns value of binomial coefficient # Code taken from https://goo.gl/vhy4jp def nCk(n, k): C = [0]* (k+1) C[0] = 1 # nC0 is 1 for i in range(1, n+1): # Compute next row of pascal triangle # using the previous row j = min(i, k) while(j>0): C[j] = C[j] + C[j-1] j = j - 1 return C[k] #function to calculate number of straight lines # can be formed def count_Straightlines(n, m): return (nCk(n, 2) - nCk(m, 2)+1) # Driven code n = 4 m = 3 print( count_Straightlines(n, m) ); # This code is contributed by "rishabh_jain".
C#
// C# program to count number of straight
// lines with n total points, out of
// which m are collinear.
using System;
public class GfG {
// Returns value of binomial coefficient
// Code taken from https://goo.gl/vhy4jp
public static int nCk(int n, int k)
{
int[] C = new int[k + 1];
// 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
// straight lines can be formed
public static int count_Straightlines(int n, int m)
{
return (nCk(n, 2) - nCk(m, 2) + 1);
}
// Driver Code
public static void Main(String []args)
{
int n = 4, m = 3;
Console.WriteLine(count_Straightlines(n, m));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to count number of straight lines
// with n total points, out of which m are
// collinear.
// Returns value of binomial coefficient
function nCk($n, $k)
{
$C = array_fill(0, $k + 1, NULL);
$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 straight lines
// can be formed
function count_Straightlines($n, $m)
{
return (nCk($n, 2) - nCk($m, 2) + 1);
}
// Driver Code
$n = 4;
$m = 3;
echo(count_Straightlines($n, $m));
// This code is contributed
// by Prasad Kshirsagar
?>
Javascript
<script>
// Javascript program to count number of straight
// lines 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 straight lines
can be formed */
function count_Straightlines(n,m)
{
return (nCk(n, 2) - nCk(m, 2)+1);
}
let n = 4, m = 3 ;
document.write(count_Straightlines(n, m));
// This code is contributed by divyesh072019.
</script>
Producción:
4
Complejidad de tiempo: O(max(n,m))
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.