Dados N triángulos junto con la longitud de sus tres lados como a, b y c . La tarea es 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.
Ejemplos:
Entrada: arr[] = {{3, 1, 2}, {2, 1, 4}, {4, 5, 6}, {6, 5, 4}, {4, 5, 6}, {5, 4, 6}};
Salida: 3Entrada: arr[] = {{4, 5, 6}, {6, 5, 4}, {1, 2, 2}, {8, 9, 12}};
Salida: 3
Este problema se resolvió usando un conjunto ordenado de STL en la publicación anterior .
Enfoque: discutiremos el enfoque basado en la sobrecarga de operadores para resolver este problema en el que vamos a sobrecargar el operador relacional (==) de nuestra clase.
- Dado que dos conjuntos cualesquiera de lados de un triángulo, digamos {4, 5, 6}, {6, 5, 4}, se dice que son iguales si cada elemento de un conjunto corresponde a los elementos del otro. Así que estaremos comparando cada elemento de un conjunto con los elementos del otro conjunto y llevaremos la cuenta. Si el conteo será el mismo, ambos conjuntos simplemente pueden considerarse iguales. Ahora simplemente hemos comparado los conjuntos usando el operador relacional para encontrar el número único de conjuntos.
- Para obtener el número de conjuntos únicos, podemos seguir el método de comparar la unicidad del conjunto actual con los conjuntos anteriores. Entonces, si habrá k conjuntos del mismo tipo, solo el último conjunto se considerará único.
A continuación se muestra la implementación en C++ del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure to represent a Triangle
// with three sides as a, b, c
struct Triangle {
int a, b, c;
public:
bool operator==(const Triangle& t) const;
};
// Function to overload relational
// operator (==)
bool Triangle::operator==(const Triangle& t) const
{
int cnt = 0;
if ((this->a == t.a)
|| (this->a == t.b)
|| (this->a == t.c)) {
cnt++;
}
if ((this->b == t.a)
|| (this->b == t.b)
|| (this->b == t.c)) {
cnt++;
}
if ((this->c == t.a)
|| (this->c == t.b)
|| (this->c == t.c)) {
cnt++;
}
// If all the three elements a, b, c
// are same, triangle is not unique
if (cnt == 3) {
return false;
}
// For unique triangle return true
return true;
}
// Function returns the number
// of unique Triangles
int countUniqueTriangles(struct Triangle arr[],
int n)
{
// Unique sets
int uni = 0;
for (int i = 0; i < n - 1; i++) {
// Check on uniqueness for a
// particular set w.r.t others
int cnt = 0;
for (int j = i; j < n - 1; j++) {
// Checks if two triangles
// are different
if (arr[i] == arr[j + 1])
cnt++;
}
// If count of unique triangles
// is same as the number of remaining
// triangles then, increment count
if (cnt == n - 1 - i)
uni++;
}
// Since last element that
// remains will be unique only
return uni + 1;
}
// Driver Code
int main()
{
// An array of structure to
// store sides of Triangles
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);
// Function Call
cout << countUniqueTriangles(arr, n);
return 0;
}
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shivamtripathi91 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA