Dado un par de puntos ‘n’, la tarea es encontrar cuatro puntos tales que formen un cuadrado cuyos lados sean paralelos a los ejes x e y o escriban «No hay tal cuadrado» de lo contrario. Si es posible más de un cuadrado, elija el que tenga el área máxima.
Ejemplos:
Entrada: n = 6, puntos = (1, 1), (4, 4), (3, 4), (4, 3), (1, 4), (4, 1)
Salida: el lado del cuadrado es : 3, los puntos del cuadrado son 1, 1 4, 1 1, 4 4, 4
Explicación: Los puntos 1, 1 4, 1 1, 4 4, 4 forman un cuadrado de lado 3Entrada: n= 6, puntos= (1, 1), (4, 5), (3, 4), (4, 3), (7, 4), (3, 1)
Salida: No hay tal cuadrado
Enfoque simple: elija todos los pares posibles de puntos con cuatro bucles anidados y luego vea si los puntos forman un cuadrado paralelo a los ejes principales. En caso afirmativo, compruebe si es el cuadrado más grande hasta ahora en términos de área y almacene el resultado, y luego muestre el resultado al final del programa. Complejidad de tiempo: O(N^4) Enfoque eficiente: Cree un bucle anidado para la esquina superior derecha e inferior izquierda del cuadrado y forme un cuadrado con esos dos puntos, luego verifique si se supuso que los otros dos puntos realmente existen. Para verificar si un punto existe o no, cree un mapa y almacene los puntos en el mapa para reducir el tiempo para verificar si los puntos existen. Además, controle el cuadrado más grande por área hasta el momento e imprímalo al final.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implemenataion of the above approach
#include <bits/stdc++.h>
using namespace std;
// find the largest square
void findLargestSquare(long long int points[][2], int n)
{
// map to store which points exist
map<pair<long long int, long long int>, int> m;
// mark the available points
for (int i = 0; i < n; i++) {
m[make_pair(points[i][0], points[i][1])]++;
}
long long int side = -1, x = -1, y = -1;
// a nested loop to choose the opposite corners of square
for (int i = 0; i < n; i++) {
// remove the chosen point
m[make_pair(points[i][0], points[i][1])]--;
for (int j = 0; j < n; j++) {
// remove the chosen point
m[make_pair(points[j][0], points[j][1])]--;
// check if the other two points exist
if (i != j
&& (points[i][0]-points[j][0]) == (points[i][1]-points[j][1])){
if (m[make_pair(points[i][0], points[j][1])] > 0
&& m[make_pair(points[j][0], points[i][1])] > 0) {
// if the square is largest then store it
if (side < abs(points[i][0] - points[j][0])
|| (side == abs(points[i][0] - points[j][0])
&& ((points[i][0] * points[i][0]
+ points[i][1] * points[i][1])
< (x * x + y * y)))) {
x = points[i][0];
y = points[i][1];
side = abs(points[i][0] - points[j][0]);
}
}
}
// add the removed point
m[make_pair(points[j][0], points[j][1])]++;
}
// add the removed point
m[make_pair(points[i][0], points[i][1])]++;
}
// display the largest square
if (side != -1)
cout << "Side of the square is : " << side
<< ", \npoints of the square are " << x << ", " << y
<< " "
<< (x + side) << ", " << y
<< " "
<< (x) << ", " << (y + side)
<< " "
<< (x + side) << ", " << (y + side) << endl;
else
cout << "No such square" << endl;
}
//Driver code
int main()
{
int n = 6;
// given points
long long int points[n][2]
= { { 1, 1 }, { 4, 4 }, { 3, 4 }, { 4, 3 }, { 1, 4 }, { 4, 1 } };
// find the largest square
findLargestSquare(points, n);
return 0;
}
Python3
# Python3 implemenataion of the above approach
# find the largest square
def findLargestSquare(points,n):
# map to store which points exist
m = dict()
# mark the available points
for i in range(n):
m[(points[i][0], points[i][1])] = \
m.get((points[i][0], points[i][1]), 0) + 1
side = -1
x = -1
y = -1
# a nested loop to choose the opposite corners of square
for i in range(n):
# remove the chosen point
m[(points[i][0], points[i][1])]-=1
for j in range(n):
# remove the chosen point
m[(points[j][0], points[j][1])]-=1
# check if the other two points exist
if (i != j and (points[i][0]-points[j][0]) == \
(points[i][1]-points[j][1])):
if (m[(points[i][0], points[j][1])] > 0 and
m[(points[j][0], points[i][1])] > 0):
# if the square is largest then store it
if (side < abs(points[i][0] - points[j][0])
or (side == abs(points[i][0] - points[j][0])
and ((points[i][0] * points[i][0]
+ points[i][1] * points[i][1])
< (x * x + y * y)))):
x = points[i][0]
y = points[i][1]
side = abs(points[i][0] - points[j][0])
# add the removed point
m[(points[j][0], points[j][1])] += 1
# add the removed point
m[(points[i][0], points[i][1])] += 1
# display the largest square
if (side != -1):
print("Side of the square is : ",side
,", \npoints of the square are ",x,", ",y
," "
,(x + side),", ",y
," "
,(x),", ",(y + side)
," "
,(x + side),", ",(y + side))
else:
print("No such square")
# Driver code
n = 6
# given points
points=[[ 1, 1 ],[ 4, 4 ],[ 3, 4 ],[ 4, 3 ],[ 1, 4 ],[ 4, 1 ] ]
# find the largest square
findLargestSquare(points, n)
# This code is contributed by mohit kumar 29
Javascript
// JavaScript implemenataion of the above approach
// find the largest square
function findLargestSquare(points, n)
{
// map to store which points exist
let m = new Map();
// mark the available points
for (let i = 0; i < n; i++) {
if(m.has([points[i][0], points[i][1]].join())){
m.set([points[i][0], points[i][1]].join(), m.get([points[i][0], points[i][1]].join() + 1));
}
else{
m.set([points[i][0], points[i][1]].join(), 1);
}
}
let side = -1, x = -1, y = -1;
// a nested loop to choose the opposite corners of square
for (let i = 0; i < n; i++) {
// remove the chosen point
m.set([points[i][0], points[i][1]].join(), m.get([points[i][0], points[i][1]].join()) - 1);
for (let j = 0; j < n; j++) {
// remove the chosen point
m.set([points[j][0], points[j][1]].join(), m.get([points[j][0], points[j][1]].join()) - 1);
// check if the other two points exist
if (i != j && (points[i][0]-points[j][0]) == (points[i][1]-points[j][1])){
if (m.get([points[i][0], points[j][j]].join()) > 0 && m.get([points[j][0], points[i][1]].join()) > 0) {
// if the square is largest then store it
if (side < Math.abs(points[i][0] - points[j][0])
|| (side == Math.abs(points[i][0] - points[j][0]) && ((points[i][0] * points[i][0] + points[i][1] * points[i][1]) < (x * x + y * y)))) {
x = points[i][0];
y = points[i][1];
side = Math.abs(points[i][0] - points[j][0]);
}
}
}
// add the removed point
m.set([points[j][0], points[j][1]].join(), m.get([points[j][0], points[j][1]].join()) + 1);
}
// add the removed point
m.set([points[i][0], points[i][1]].join(), m.get([points[i][0], points[i][1]].join()) + 1);
}
// display the largest square
if (side != -1){
console.log("Side of the square is :", side, ", ");
console.log("points of the square are", x, ",", y, x + side, ",", y, x, ",", y + side, x + side, ",", y + side);
}
else
console.log("No such square");
}
//Driver code
let n = 6;
// given points
let points = [[1, 1 ], [4, 4], [3, 4], [4, 3], [1, 4], [4, 1]];
// find the largest square
findLargestSquare(points, n);
// The code is contributed by Nidhi goel
Side of the square is : 3, points of the square are 1, 1 4, 1 1, 4 4, 4
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA