Dados cuatro puntos en un espacio bidimensional, necesitamos averiguar si forman un paralelogramo o no.
Un paralelogramo tiene cuatro lados. Dos lados opuestos son paralelos y tienen la misma longitud.
Ejemplos:
Points = [(0, 0), (4, 0), (1, 3), (5, 3)] Above points make a parallelogram. Points = [(0, 0), (2, 0), (4, 0), (2, 2)] Above points does not make a parallelogram as first three points itself are linear.
Los problemas para verificar cuadrados y rectángulos se pueden leer en Verificación de cuadrados y Verificación de rectángulospero en este problema, necesitamos verificar el paralelogramo. Las principales propiedades del paralelogramo son que los lados opuestos del paralelogramo son paralelos y de igual longitud y las diagonales del paralelogramo se bisecan entre sí. Usamos la segunda propiedad para resolver este problema. Como hay cuatro puntos, podemos obtener un total de 6 puntos medios considerando cada par. Ahora, para que cuatro puntos formen un paralelogramo, 2 de los puntos medios deben ser iguales y el resto debe ser diferente. En el siguiente código, hemos creado un mapa que almacena los pares correspondientes a cada punto medio. Después de calcular todos los puntos medios, iteramos sobre el mapa y verificamos la ocurrencia de cada punto medio. Si exactamente un punto medio ocurrió dos veces y otro ocurrió una vez, entonces, dados cuatro puntos, haga un paralelogramo; de lo contrario, no.
CPP
// C++ code to test whether four points make a
// parallelogram or not
#include <bits/stdc++.h>
using namespace std;
// structure to represent a point
struct point {
double x, y;
point() { }
point(double x, double y)
: x(x), y(y) { }
// defining operator < to compare two points
bool operator<(const point& other) const
{
if (x < other.x) {
return true;
} else if (x == other.x) {
if (y < other.y) {
return true;
}
}
return false;
}
};
// Utility method to return mid point of two points
point getMidPoint(point points[], int i, int j)
{
return point((points[i].x + points[j].x) / 2.0,
(points[i].y + points[j].y) / 2.0);
}
// method returns true if point of points array form
// a parallelogram
bool isParallelogram(point points[])
{
map<point, vector<point> > midPointMap;
// looping over all pairs of point to store their
// mid points
int P = 4;
for (int i = 0; i < P; i++) {
for (int j = i + 1; j < P; j++) {
point temp = getMidPoint(points, i, j);
// storing point pair, corresponding to
// the mid point
midPointMap[temp].push_back(point(i, j));
}
}
int two = 0, one = 0;
// looping over (midpoint, (corresponding pairs))
// map to check the occurrence of each midpoint
for (auto x : midPointMap) {
// updating midpoint count which occurs twice
if (x.second.size() == 2)
two++;
// updating midpoing count which occurs once
else if (x.second.size() == 1)
one++;
// if midpoint count is more than 2, then
// parallelogram is not possible
else
return false;
}
// for parallelogram, one mid point should come
// twice and other mid points should come once
if (two == 1 && one == 4)
return true;
return false;
}
// Driver code to test above methods
int main()
{
point points[4];
points[0] = point(0, 0);
points[1] = point(4, 0);
points[2] = point(1, 3);
points[3] = point(5, 3);
if (isParallelogram(points))
cout << "Given points form a parallelogram";
else
cout << "Given points does not form a "
"parallelogram";
return 0;
}
Producción:
Given points form a parallelogram
Complejidad de Tiempo: O(p 2 logp) , donde p es el número de puntos
Espacio Auxiliar: O(p 2 ), donde p es el número de puntos
Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . 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