Dado un conjunto L = {l 1 , l 2 , ………, l n } de ‘n’ líneas distintas en el Plano Euclidiano. La i -ésima línea está dada por una ecuación en la forma a i x + b i y = c i . Halla el número de triángulos que se pueden formar usando las rectas del conjunto L. Ten en cuenta que no hay dos pares de rectas que se crucen en el mismo punto.
Nota: este problema no menciona que las líneas no pueden ser paralelas, lo que dificulta la solución del problema.
Ejemplos:
Input: a[] = {1, 2, 3, 4}
b[] = {2, 4, 5, 5}
c[] = {5, 7, 8, 6}
Output: 2
The number of triangles that can be formed are: 2
Input: a[] = {1, 2, 3, 2, 4, 1, 2, 3, 4, 5}
b[] = {2, 4, 6, 3, 6, 5, 10, 15, 20, 25}
c[] = {3, 5, 11, 10, 9, 17, 13, 11, 7, 3}
Output: 30
The number of triangles that can be formed are: 30
Algoritmo ingenuo
El algoritmo ingenuo se puede describir como:
- Recoge 3 líneas arbitrarias del conjunto L.
- Ahora comprueba si se puede formar un triángulo usando las 3 líneas seleccionadas. Esto se puede hacer fácilmente verificando que ninguno de ellos sea paralelo por pares.
- Incrementa el contador si se puede formar el triángulo.
Complejidad de tiempo: Hay n C 3 tripletas de líneas. Para cada triplete, tenemos que hacer 3 comparaciones para verificar que las 2 líneas no sean paralelas, lo que significa que la verificación se puede realizar en tiempo O(1). Esto hace que el algoritmo ingenuo sea O(n 3 ).
Algoritmo eficiente
Esto también se puede lograr en O(n log n). La lógica detrás del algoritmo eficiente se describe a continuación.
Dividimos el conjunto L en varios subconjuntos. La formación de subconjuntos se basa en pendientes, es decir, todas las líneas de un subconjunto particular tienen la misma pendiente, es decir, son paralelas entre sí.
Consideremos tres conjuntos (digamos A, B y C). Para un conjunto particular (digamos A) las líneas que pertenecen a este son todas paralelas entre sí. Si tenemos A, B y C, podemos elegir una línea de cada conjunto para obtener un triángulo porque ninguna de estas líneas será paralela. Al hacer los subconjuntos, nos aseguramos de que no se junten dos líneas paralelas.
Ahora, si tenemos solo estos 3 subconjuntos ,
Number of triangles = (Number of ways to pick a line from A) *
(Number of ways to pick a line from B) *
(Number of ways to pick a line from C)
= m1*m2*m3
Here m1 is count of elements with first slope (in Set A)
Here m2 is count of elements with first slope (in Set B)
Here m3 is count of elements with first slope (in Set C)
De manera similar, si tenemos 4 subconjuntos , podemos extender esta lógica para obtener
Número de triángulos = m1*m2*m3 + m1*m2*m4 + m1*m3*m4 + m2*m3*m4
Para un número de subconjuntos mayor que 3, si tenemos ‘k’ subconjuntos, nuestra tarea es encontrar la suma del número de elementos del subconjunto tomando 3 a la vez. Esto se puede hacer manteniendo una array de conteo. Hacemos una array de conteo donde conteo i denota el conteo del subconjunto i -ésimo de líneas paralelas.
We one by one compute following values. sum1 = m1 + m2 + m3 ..... sum2 = m1*m2 + m1*m3 + ... + m2*m3 + m2*m4 + ... sum3 = m1*m2*m3 + m1*m2*m4 + ...... m2*m3*m4 + .... sum3 gives our final answer
C++
// C++ program to find the number of
// triangles that can be formed
// using a set of lines in Euclidean
// Plane
#include <bits/stdc++.h>
using namespace std;
#define EPSILON numeric_limits<double>::epsilon()
// double variables can't be checked precisely
// using '==' this function returns true if
// the double variables are equal
bool compareDoubles(double A, double B)
{
double diff = A-B;
return (diff<EPSILON) && (-diff<EPSILON);
}
// This function returns the number of triangles
// for a given set of lines
int numberOfTringles(int a[], int b[], int c[], int n)
{
//slope array stores the slope of lines
double slope[n];
for (int i=0; i<n; i++)
slope[i] = (a[i]*1.0)/b[i];
// slope array is sorted so that all lines
// with same slope come together
sort(slope, slope+n);
// After sorting slopes, count different
// slopes. k is index in count[].
int count[n], k = 0;
int this_count = 1; // Count of current slope
for (int i=1; i<n; i++)
{
if (compareDoubles(slope[i], slope[i-1]))
this_count++;
else
{
count[k++] = this_count;
this_count = 1;
}
}
count[k++] = this_count;
// calculating sum1 (Sum of all slopes)
// sum1 = m1 + m2 + ...
int sum1 = 0;
for (int i=0; i<k; i++)
sum1 += count[i];
// calculating sum2. sum2 = m1*m2 + m2*m3 + ...
int sum2 = 0;
int temp[n]; // Needed for sum3
for (int i=0; i<k; i++)
{
temp[i] = count[i]*(sum1-count[i]);
sum2 += temp[i];
}
sum2 /= 2;
// calculating sum3 which gives the final answer
// m1 * m2 * m3 + m2 * m3 * m4 + ...
int sum3 = 0;
for (int i=0; i<k; i++)
sum3 += count[i]*(sum2-temp[i]);
sum3 /= 3;
return sum3;
}
// Driver code
int main()
{
// lines are stored as arrays of a, b
// and c for 'ax+by=c'
int a[] = {1, 2, 3, 4};
int b[] = {2, 4, 5, 5};
int c[] = {5, 7, 8, 6};
// n is the number of lines
int n = sizeof(a)/sizeof(a[0]);
cout << "The number of triangles that"
" can be formed are: "
<< numberOfTringles(a, b, c, n);
return 0;
}
Java
// Java program to find the number of
// triangles that can be formed
// using a set of lines in Euclidean
// Plane
import java.util.*;
class GFG{
static double EPSILON = 1.0842e-19;
// Double variables can't be checked precisely
// using '==' this function returns true if
// the double variables are equal
static boolean compareDoubles(double A, double B)
{
double diff = A - B;
return (diff < EPSILON) &&
(-diff < EPSILON);
}
// This function returns the number of
// triangles for a given set of lines
static int numberOfTringles(int []a, int []b,
int []c, int n)
{
// Slope array stores the slope of lines
Vector<Double> slope = new Vector<>();
for(int i = 0; i < n; i++)
slope.add((double)(a[i] * 1.0) / b[i]);
// Slope array is sorted so that all lines
// with same slope come together
Collections.sort(slope);
// After sorting slopes, count different
// slopes. k is index in count[].
int []count = new int [n];
int k = 0;
// Count of current slope
int this_count = 1;
for(int i = 1; i < n; i++)
{
if (compareDoubles((double)slope.get(i),
(double)slope.get(i - 1)))
this_count++;
else
{
count[k++] = this_count;
this_count = 1;
}
}
count[k++] = this_count;
// Calculating sum1 (Sum of all slopes)
// sum1 = m1 + m2 + ...
int sum1 = 0;
for(int i = 0; i < k; i++)
sum1 += count[i];
// Calculating sum2. sum2 = m1*m2 + m2*m3 + ...
int sum2 = 0;
// Needed for sum3
int temp[] = new int [n];
for(int i = 0; i < k; i++)
{
temp[i] = count[i] * (sum1 - count[i]);
sum2 += temp[i];
}
sum2 /= 2;
// Calculating sum3 which gives the
// final answer
// m1 * m2 * m3 + m2 * m3 * m4 + ...
int sum3 = 0;
for(int i = 0; i < k; i++)
sum3 += count[i] * (sum2 - temp[i]);
sum3 /= 3;
return sum3;
}
// Driver code
public static void main(String[] args)
{
// Lines are stored as arrays of a, b
// and c for 'ax+by=c'
int a[] = { 1, 2, 3, 4 };
int b[] = { 2, 4, 5, 5 };
int c[] = { 5, 7, 8, 6 };
// n is the number of lines
int n = a.length;
System.out.println("The number of triangles " +
"that can be formed are: " +
numberOfTringles(a, b, c, n));
}
}
// This code is contributed by Stream_Cipher
Python3
# Python program to find the number of
# triangles that can be formed
# using a set of lines in Euclidean
# Plane
import math
EPSILON = 1.0842e-19
# double variables can't be checked precisely
# using '==' this function returns true if
# the double variables are equal
def compareDoubles(A, B):
diff = A-B
return (diff < EPSILON) and (-diff < EPSILON)
# This function returns the number of triangles
# for a given set of lines
def numberOfTringles(a, b, c, n):
# slope array stores the slope of lines
slope = []
for i in range(0, n):
slope.append((a[i]*1.0)/b[i])
# slope array is sorted so that all lines
# with same slope come together
slope.sort()
# After sorting slopes, count different
# slopes. k is index in count[].
k = 0
count = []
this_count = 1 # Count of current slope
for i in range(1, n):
if compareDoubles(slope[i], slope[i-1]):
this_count = this_count + 1
else:
count.append(this_count)
k = k + 1
this_count = 1
count.append(this_count)
k = k + 1
# calculating sum1 (Sum of all slopes)
# sum1 = m1 + m2 + ...
sum1 = 0
for i in range(0, k):
sum1 += count[i]
# calculating sum2. sum2 = m1*m2 + m2*m3 + ...
sum2 = 0
temp = [] # Needed for sum3
for i in range(0, k):
temp.append(count[i]*(sum1-count[i]))
sum2 += temp[i]
sum2 = math.floor(sum2/2)
# calculating sum3 which gives the final answer
# m1 * m2 * m3 + m2 * m3 * m4 + ...
sum3 = 0
for i in range(0, k):
sum3 += count[i]*(sum2-temp[i])
sum3 = math.floor(sum3/3)
return sum3
# Driver Code
# lines are stored as arrays of a, b
# and c for 'ax+by=c'
a = [1, 2, 3, 4]
b = [2, 4, 5, 5]
c = [5, 7, 8, 6]
# n is the number of lines
n = len(a)
print("The number of triangles that can be formed are: ",
numberOfTringles(a, b, c, n))
# The code is contributed by Gautam goel (gautamgoel962)
C#
// C# program to find the number of
// triangles that can be formed
// using a set of lines in Euclidean
// Plane
using System.Collections.Generic;
using System;
class GFG{
static double EPSILON = 1.0842e-19;
// Double variables can't be checked precisely
// using '==' this function returns true if
// the double variables are equal
static bool compareDoubles(double A, double B)
{
double diff = A - B;
return (diff < EPSILON) &&
(-diff < EPSILON);
}
// This function returns the number of
// triangles for a given set of lines
static int numberOfTringles(int []a, int []b,
int []c, int n)
{
// Slope array stores the slope of lines
List<double> slope = new List<double>();
for(int i = 0; i < n; i++)
slope.Add((double)(a[i] * 1.0) / b[i]);
// Slope array is sorted so that all lines
// with same slope come together
slope.Sort();
// After sorting slopes, count different
// slopes. k is index in count[].
int []count = new int [n];
int k = 0;
// Count of current slope
int this_count = 1;
for(int i = 1; i < n; i++)
{
if (compareDoubles((double)slope[i],
(double)slope[i - 1]))
this_count++;
else
{
count[k++] = this_count;
this_count = 1;
}
}
count[k++] = this_count;
// Calculating sum1 (Sum of all slopes)
// sum1 = m1 + m2 + ...
int sum1 = 0;
for(int i = 0; i < k; i++)
sum1 += count[i];
// Calculating sum2. sum2 = m1*m2 + m2*m3 + ...
int sum2 = 0;
// Needed for sum3
int []temp = new int [n];
for(int i = 0; i < k; i++)
{
temp[i] = count[i] * (sum1 - count[i]);
sum2 += temp[i];
}
sum2 /= 2;
// Calculating sum3 which gives
// the final answer
// m1 * m2 * m3 + m2 * m3 * m4 + ...
int sum3 = 0;
for(int i = 0; i < k; i++)
sum3 += count[i] * (sum2 - temp[i]);
sum3 /= 3;
return sum3;
}
// Driver code
public static void Main()
{
// lines are stored as arrays of a, b
// and c for 'ax+by=c'
int []a = { 1, 2, 3, 4 };
int []b = { 2, 4, 5, 5 };
int []c = { 5, 7, 8, 6 };
// n is the number of lines
int n = a.Length;
Console.WriteLine("The number of triangles " +
"that can be formed are: " +
numberOfTringles(a, b, c, n));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// JavaScript program to find the number of
// triangles that can be formed
// using a set of lines in Euclidean
// Plane
const EPSILON = 1.0842e-19;
// Double variables can't be checked precisely
// using '==' this function returns true if
// the double variables are equal
function compareDoubles(A, B) {
var diff = A - B;
return diff < EPSILON && -diff < EPSILON;
}
// This function returns the number of
// triangles for a given set of lines
function numberOfTringles(a, b, c, n) {
// Slope array stores the slope of lines
var slope = [];
for (var i = 0; i < n; i++) slope.push(parseFloat(a[i] * 1.0) / b[i]);
// Slope array is sorted so that all lines
// with same slope come together
slope.sort();
// After sorting slopes, count different
// slopes. k is index in count[].
var count = new Array(n).fill(0);
var k = 0;
// Count of current slope
var this_count = 1;
for (var i = 1; i < n; i++) {
if (compareDoubles(parseFloat(slope[i]), parseFloat(slope[i - 1])))
this_count++;
else {
count[k++] = this_count;
this_count = 1;
}
}
count[k++] = this_count;
// Calculating sum1 (Sum of all slopes)
// sum1 = m1 + m2 + ...
var sum1 = 0;
for (var i = 0; i < k; i++) sum1 += count[i];
// Calculating sum2. sum2 = m1*m2 + m2*m3 + ...
var sum2 = 0;
// Needed for sum3
var temp = new Array(n).fill(0);
for (var i = 0; i < k; i++) {
temp[i] = count[i] * (sum1 - count[i]);
sum2 += temp[i];
}
sum2 /= 2;
// Calculating sum3 which gives
// the final answer
// m1 * m2 * m3 + m2 * m3 * m4 + ...
var sum3 = 0;
for (var i = 0; i < k; i++) sum3 += count[i] * (sum2 - temp[i]);
sum3 /= 3;
return sum3;
}
// Driver code
// lines are stored as arrays of a, b
// and c for 'ax+by=c'
var a = [1, 2, 3, 4];
var b = [2, 4, 5, 5];
var c = [5, 7, 8, 6];
// n is the number of lines
var n = a.length;
document.write(
"The number of triangles " +
"that can be formed are: " +
numberOfTringles(a, b, c, n)
);
// This code is contributed by rdtank.
</script>
Producción:
The number of triangles that can be formed are: 2
Complejidad de tiempo: todos los bucles en el código son O (n). La complejidad del tiempo en esta implementación está impulsada por la función de clasificación utilizada para clasificar la array de pendientes. Esto hace que el algoritmo sea O(nlogn).
Espacio Auxiliar : O(n)
Este artículo es una contribución de Aarti_Rathi y Aanya Jindal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA