Dada una array de puntos puntos[] en un sistema de coordenadas cartesianas, la tarea es encontrar el número de cuadrados que son paralelos al eje de coordenadas.
Ejemplos:
Entrada: puntos[] = {(0, 0), (0, 2), (2, 0), (2, 2), (1, 1)}
Salida: 1
Explicación:
Como los puntos (0, 0) , (0, 2), (2, 0), (2, 2) forman un cuadrado que es paralelo al eje X y al eje Y, por lo tanto, el recuento de tales cuadrados es 1.Entrada: puntos[] = {(2, 0), (0, 2), (2, 2), (0, 0), (-2, 2), (-2, 0)}
Salida: 2
Explicación:
Como los puntos (0, 0), (0, 2), (2, 0), (2, 2) forman un cuadrado, mientras que los puntos (0, 0), (0, 2), (-2, 0) , (-2, 2) forma otro cuadrado que es paralelo al eje X y al eje Y, por
lo tanto, la cuenta de tales cuadrados es 2.
Enfoque: la idea es elegir dos puntos de la array de puntos de manera que estos dos puntos sean paralelos al eje de coordenadas y luego encontrar otros dos puntos del cuadrado con la ayuda de la distancia entre los puntos. Si esos puntos existen en la array, entonces, existe un cuadrado posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find count of Squares
// that are parallel to the coordinate axis
// from the given set of N points
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
// Function to get distance
// between two points
int get_dis(pair<int, int> p1,
pair<int, int> p2)
{
int a = abs(p1.first - p2.first);
int b = abs(p1.second - p2.second);
return ((a * a) + (b * b));
}
// Function to check that points
// forms a square and parallel to
// the co-ordinate axis
bool check(pair<int, int> p1,
pair<int, int> p2,
pair<int, int> p3,
pair<int, int> p4)
{
int d2 = get_dis(p1, p2);
int d3 = get_dis(p1, p3);
int d4 = get_dis(p1, p4);
if (d2 == d3
&& 2 * d2 == d4
&& 2 * get_dis(p2, p4) == get_dis(p2, p3)) {
return true;
}
if (d3 == d4
&& 2 * d3 == d2
&& 2 * get_dis(p3, p2) == get_dis(p3, p4)) {
return true;
}
if (d2 == d4
&& 2 * d2 == d3
&& 2 * get_dis(p2, p3) == get_dis(p2, p4)) {
return true;
}
return false;
}
// Function to find all the squares which is
// parallel to co-ordinate axis
int count(map<pair<int, int>, int> hash,
vector<pair<int, int> > v, int n)
{
int ans = 0;
map<pair<int, int>, int> vis;
// Loop to choose two points
// from the array of points
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
pair<int, int> p1
= make_pair(v[i].first,
v[j].second);
pair<int, int> p2
= make_pair(v[j].first,
v[i].second);
set<pair<int, int> > s;
s.insert(v[i]);
s.insert(v[j]);
s.insert(p1);
s.insert(p2);
if (sz(s) != 4)
continue;
// Condition to check if the
// other points are present in the map
if (hash.find(p1) != hash.end()
&& hash.find(p2) != hash.end()) {
if ((!vis[v[i]] || !vis[v[j]]
|| !vis[p1] || !vis[p2])
&& (check(v[i], v[j], p1, p2))) {
vis[v[i]] = 1;
vis[v[j]] = 1;
vis[p1] = 1;
vis[p2] = 1;
ans++;
}
}
}
}
cout << ans;
return ans;
}
// Function to Count the number of squares
void countOfSquares(vector<pair<int, int> > v, int n)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
map<pair<int, int>, int> hash;
// Declaring iterator to a vector
vector<pair<int, int> >::iterator ptr;
// Adding the points to hash
for (ptr = v.begin(); ptr < v.end(); ptr++)
hash[*ptr] = 1;
// Count the number of squares
count(hash, v, n);
}
// Driver Code
int main()
{
int n = 5;
vector<pair<int, int> > v;
v.push_back(make_pair(0, 0));
v.push_back(make_pair(0, 2));
v.push_back(make_pair(2, 0));
v.push_back(make_pair(2, 2));
v.push_back(make_pair(0, 1));
// Function call
countOfSquares(v, n);
return 0;
}
1
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay dos bucles que requieren un tiempo O(N 2 ), por lo que la complejidad de tiempo será O(N 2 ) .
- Complejidad del espacio auxiliar: como en el enfoque anterior, se utiliza espacio adicional, por lo que la complejidad del espacio auxiliar será O(N) .