Se nos dan n triángulos junto con la longitud de sus tres lados como a, b, c. Ahora necesitamos contar el número de triángulos únicos de estos n triángulos dados. Dos triángulos son diferentes entre sí si tienen al menos uno de los lados diferente.

Ejemplo:

Input: arr[] = {{1, 2, 2},
                {4, 5, 6}, 
                {4, 5, 6}    
Output: 2

Input: arr[] = {{4, 5, 6}, {6, 5, 4},
                {1, 2, 2}, {8, 9, 12}
Output: 3

Le recomendamos encarecidamente que minimice su navegador e intente esto usted mismo primero.

Como se nos pide que encontremos el número de triángulos “únicos”, podemos usar colocar o unordered_set. En esta publicación, se analiza el enfoque basado en conjuntos.

¿Cómo almacenar tres lados como elemento en el contenedor? Usamos STL par para almacenar los tres lados juntos como

pair <int, pair<int, int> >

Insertamos uno por uno todos los triángulos en el conjunto. Pero el problema con este enfoque es que un triángulo con lados como {4, 5, 6} es diferente de un triángulo con lados {5, 4, 6} aunque se refieren a un mismo triángulo.

Para manejar estos casos, almacenamos los lados en orden ordenado (en función de la longitud de los lados), aquí la clasificación no será un problema ya que solo tenemos 3 lados y podemos clasificarlos en un tiempo constante. Por ejemplo, {5, 4, 6} se inserta en el conjunto como {4, 5, 6}

Nota: Podemos hacer un par con make_pair (a, b) o simplemente podemos usar {a, b}.

A continuación se muestra la implementación en C ++ de la idea anterior:

#include <bits/stdc++.h>

using namespace std;

 

typedef pair<int, int> iPair;

 

struct Triangle

{

    int a, b, c;

};

 

int sort3(int &a, int &b, int &c)

{

    if (a > b) swap(a, b);

    if (b > c) swap(b, c);

    if (a > b) swap(a, b);

}

 

int countUniqueTriangles(struct Triangle arr[],

                           int n)

{

    

    set < pair< int, iPair > > s;

 

    

    for (int i=0; i<n; i++)

    {

        

        int a = arr[i].a, b = arr[i].b, c = arr[i].c;

        sort3(a, b, c);

 

        

        s.insert({a, {b, c}});

    }

 

    

    return s.size();

}

 

int main()

{

    

    struct Triangle arr[] = {{3, 2, 2}, {3, 4, 5}, {1, 2, 2},

                             {2, 2, 3}, {5, 4, 3}, {6, 4, 5}};

    int n = sizeof(arr)/sizeof(Triangle);

 

    cout << "Number of Unique Triangles are "

         << countUniqueTriangles(arr, n);

    return 0;

}

Producción:

Number of Unique Triangles are 4

La complejidad temporal de la solución anterior es O (n Log n), ya que el conjunto requiere un tiempo O (Log n) para la inserción.

Podemos mejorar la complejidad del tiempo a O (n) usando unordered_set. Pero el uso de unordered_set requiere la escritura de una función hash, ya que la función hash no está definida en la biblioteca para pares.

Artículo relacionado: Número de triángulos posibles

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *