Dadas las coordenadas de cuatro puntos en un plano, encuentre si los cuatro puntos forman un cuadrado o no.
Para verificar el cuadrado, debemos verificar lo siguiente.
a) Todos los cuatro lados formados por puntos son iguales.
b) El ángulo entre dos lados cualesquiera es de 90 grados. (Esta condición es necesaria ya que el cuadrilátero también tiene los mismos lados.
c) Verifica que ambas diagonales tengan la misma distancia
Ejemplos:
Entrada: p1 = { 20, 10 }, p2 = { 10, 20 }, p3 = { 20, 20 }, p4 = { 10, 10 } Salida:
Sí Explicación
:
Entrada: p1 = { 20, 20 }, p2 = { 10, 20 }, p3 = { 20, 20 }, p4 = { 10, 10 } Salida
: No
Aproximación: La idea es escoger cualquier punto y calcular su distancia al resto de puntos. Deje que el punto elegido sea ‘p’. Para formar un cuadrado, la distancia de dos puntos debe ser la misma desde ‘p’, sea esta distancia d. La distancia desde un punto debe ser diferente de la d y debe ser igual a √2 veces d. Sea este punto con diferente distancia ‘q’.
La condición anterior no es lo suficientemente buena ya que el punto con una distancia diferente puede estar en el otro lado. También tenemos que comprobar que q está a la misma distancia de otros 2 puntos y esta distancia es la misma que d.
A continuación se muestran las implementaciones de la idea anterior.
C++
// A C++ program to check if four given points form a square or not.
#include <iostream>
using namespace std;
// Structure of a point in 2D space
struct Point {
int x, y;
};
// A utility function to find square of distance
// from point 'p' to point 'q'
int distSq(Point p, Point q)
{
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}
// This function returns true if (p1, p2, p3, p4) form a
// square, otherwise false
bool isSquare(Point p1, Point p2, Point p3, Point p4)
{
int d2 = distSq(p1, p2); // from p1 to p2
int d3 = distSq(p1, p3); // from p1 to p3
int d4 = distSq(p1, p4); // from p1 to p4
if (d2 == 0 || d3 == 0 || d4 == 0)
return false;
// If lengths if (p1, p2) and (p1, p3) are same, then
// following conditions must met to form a square.
// 1) Square of length of (p1, p4) is same as twice
// the square of (p1, p2)
// 2) Square of length of (p2, p3) is same
// as twice the square of (p2, p4)
if (d2 == d3 && 2 * d2 == d4
&& 2 * distSq(p2, p4) == distSq(p2, p3)) {
return true;
}
// The below two cases are similar to above case
if (d3 == d4 && 2 * d3 == d2
&& 2 * distSq(p3, p2) == distSq(p3, p4)) {
return true;
}
if (d2 == d4 && 2 * d2 == d3
&& 2 * distSq(p2, p3) == distSq(p2, p4)) {
return true;
}
return false;
}
// Driver program to test above function
int main()
{
Point p1 = { 20, 10 }, p2 = { 10, 20 },
p3 = { 20, 20 }, p4 = { 10, 10 };
isSquare(p1, p2, p3, p4) ? cout << "Yes" : cout << "No";
return 0;
}
Java
// A Java program to check if four given points form a square or not.
class GFG
{
// Structure of a point in 2D space
static class Point
{
int x, y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// A utility function to find square of distance
// from point 'p' to point 'q'
static int distSq(Point p, Point q)
{
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}
// This function returns true if (p1, p2, p3, p4) form a
// square, otherwise false
static boolean isSquare(Point p1, Point p2, Point p3, Point p4)
{
int d2 = distSq(p1, p2); // from p1 to p2
int d3 = distSq(p1, p3); // from p1 to p3
int d4 = distSq(p1, p4); // from p1 to p4
if (d2 == 0 || d3 == 0 || d4 == 0)
return false;
// If lengths if (p1, p2) and (p1, p3) are same, then
// following conditions must met to form a square.
// 1) Square of length of (p1, p4) is same as twice
// the square of (p1, p2)
// 2) Square of length of (p2, p3) is same
// as twice the square of (p2, p4)
if (d2 == d3 && 2 * d2 == d4
&& 2 * distSq(p2, p4) == distSq(p2, p3))
{
return true;
}
// The below two cases are similar to above case
if (d3 == d4 && 2 * d3 == d2
&& 2 * distSq(p3, p2) == distSq(p3, p4))
{
return true;
}
if (d2 == d4 && 2 * d2 == d3
&& 2 * distSq(p2, p3) == distSq(p2, p4))
{
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
Point p1 = new Point(20, 10), p2 = new Point( 10, 20 ),
p3 = new Point(20, 20 ), p4 = new Point( 10, 10 );
System.out.println(isSquare(p1, p2, p3, p4)==true ? "Yes" : "No");
}
}
// This code is contributed by PrinciRaj1992
Python3
# A Python3 program to check if
# four given points form a square or not.
class Point:
# Structure of a point in 2D space
def __init__(self, x, y):
self.x = x
self.y = y
# A utility function to find square of
# distance from point 'p' to point 'q'
def distSq(p, q):
return (p.x - q.x) * (p.x - q.x) +\
(p.y - q.y) * (p.y - q.y)
# This function returns true if (p1, p2, p3, p4)
# form a square, otherwise false
def isSquare(p1, p2, p3, p4):
d2 = distSq(p1, p2) # from p1 to p2
d3 = distSq(p1, p3) # from p1 to p3
d4 = distSq(p1, p4) # from p1 to p4
if d2 == 0 or d3 == 0 or d4 == 0:
return False
# If lengths if (p1, p2) and (p1, p3) are same, then
# following conditions must be met to form a square.
# 1) Square of length of (p1, p4) is same as twice
# the square of (p1, p2)
# 2) Square of length of (p2, p3) is same
# as twice the square of (p2, p4)
if d2 == d3 and 2 * d2 == d4 and \
2 * distSq(p2, p4) == distSq(p2, p3):
return True
# The below two cases are similar to above case
if d3 == d4 and 2 * d3 == d2 and \
2 * distSq(p3, p2) == distSq(p3, p4):
return True
if d2 == d4 and 2 * d2 == d3 and \
2 * distSq(p2, p3) == distSq(p2, p4):
return True
return False
# Driver Code
if __name__=="__main__":
p1 = Point(20, 10)
p2 = Point(10, 20)
p3 = Point(20, 20)
p4 = Point(10, 10)
if isSquare(p1, p2, p3, p4):
print('Yes')
else:
print('No')
# This code is contributed by Mayank Chaudhary
# aka chaudhary_19
C#
// A C# program to check if four given points form a square or not.
using System;
class GFG
{
// Structure of a point in 2D space
class Point
{
public int x, y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// A utility function to find square of distance
// from point 'p' to point 'q'
static int distSq(Point p, Point q)
{
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}
// This function returns true if (p1, p2, p3, p4) form a
// square, otherwise false
static bool isSquare(Point p1, Point p2, Point p3, Point p4)
{
int d2 = distSq(p1, p2); // from p1 to p2
int d3 = distSq(p1, p3); // from p1 to p3
int d4 = distSq(p1, p4); // from p1 to p4
if (d2 == 0 || d3 == 0 || d4 == 0)
return false;
// If lengths if (p1, p2) and (p1, p3) are same, then
// following conditions must met to form a square.
// 1) Square of length of (p1, p4) is same as twice
// the square of (p1, p2)
// 2) Square of length of (p2, p3) is same
// as twice the square of (p2, p4)
if (d2 == d3 && 2 * d2 == d4
&& 2 * distSq(p2, p4) == distSq(p2, p3))
{
return true;
}
// The below two cases are similar to above case
if (d3 == d4 && 2 * d3 == d2
&& 2 * distSq(p3, p2) == distSq(p3, p4))
{
return true;
}
if (d2 == d4 && 2 * d2 == d3
&& 2 * distSq(p2, p3) == distSq(p2, p4))
{
return true;
}
return false;
}
// Driver code
public static void Main(String[] args)
{
Point p1 = new Point(20, 10), p2 = new Point(10, 20),
p3 = new Point(20, 20), p4 = new Point(10, 10);
Console.WriteLine(isSquare(p1, p2, p3, p4) == true ? "Yes" : "No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to check if four given points form a square or not.
// A utility function to find square of distance
// from point 'p' to point 'q'
function distSq( p, q){
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}
// This function returns true if (p1, p2, p3, p4) form a
// square, otherwise false
function isSquare(p1, p2, p3, p4){
let d2 = distSq(p1, p2); // from p1 to p2
let d3 = distSq(p1, p3); // from p1 to p3
let d4 = distSq(p1, p4); // from p1 to p4
if (d2 == 0 || d3 == 0 || d4 == 0)
return false;
// If lengths if (p1, p2) and (p1, p3) are same, then
// following conditions must met to form a square.
// 1) Square of length of (p1, p4) is same as twice
// the square of (p1, p2)
// 2) Square of length of (p2, p3) is same
// as twice the square of (p2, p4)
if (d2 == d3 && 2 * d2 == d4
&& 2 * distSq(p2, p4) == distSq(p2, p3)) {
return true;
}
// The below two cases are similar to above case
if (d3 == d4 && 2 * d3 == d2
&& 2 * distSq(p3, p2) == distSq(p3, p4)) {
return true;
}
if (d2 == d4 && 2 * d2 == d3
&& 2 * distSq(p2, p3) == distSq(p2, p4)) {
return true;
}
return false;
}
// Driver program to test above function
let p1 = { x:20, y:10 }
let p2 = { x:10, y:20 }
let p3 = { x:20, y:20 }
let p4 = { x:10, y:10 }
isSquare(p1, p2, p3, p4) ? document.write("Yes") : document.write("No");
// This code is contributed by rohitsingh07052.
</script>
Producción
Yes
Complejidad de tiempo: O(1), todas las operaciones se realizan en tiempo constante O(1).
Espacio auxiliar: O(1), no se requiere espacio adicional
Problema extendido:
Este artículo es una contribución de Anuj . 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