Máximo de cuadrados posibles paralelos a ambos ejes desde N puntos distintos

Dadas las coordenadas X _i e Y _i de N puntos distintos en el plano 2-D, la tarea es contar el número de cuadrados que se pueden formar a partir de estos puntos que son paralelos a los ejes X e Y.
Ejemplos: 
 

Entrada: X[] = { 0, 2, 0, 2 }, Y[] = { 0, 2, 2, 0 } 
Salida: 1 
Explicación: Solo se puede formar un cuadrado usando estos puntos – 
(0, 2)( 2, 2) 
(0, 0)(2, 0) 
Entrada: X[] = { 3, 2, 0, 6 }, Y[] = { 0, 2, 0, 6 } 
Salida: 0 
Explicación: Sin cuadrado se puede formar usando estos puntos – 
(3,0), (2,0), (0,0), (6,6) 
 

Enfoque ingenuo: iterar sobre todas las combinaciones posibles de cuatro puntos y verificar si se puede formar un cuadrado que sea paralelo a los ejes X e Y. La complejidad temporal de este enfoque sería O(N ⁴ ) . 
Enfoque eficiente: podemos observar que para que cuatro puntos formen un cuadrado requerido, las siguientes condiciones deben cumplirse: 
 

• Los puntos que se encuentran en la misma línea horizontal deben tener las mismas coordenadas Y.

• Los puntos que se encuentran en la misma línea vertical deben tener las mismas coordenadas X.

• La distancia entre estos puntos debe ser la misma.

Así, los cuatro puntos de cualquier cuadrado se pueden escribir como P1(X ₁ , Y ₁ ), P2(X ₂ , Y ₁ ), P3(X ₂ , Y ₂ ) y P4(X ₁ , Y ₂ ) en el sentido de las agujas del reloj. 
Considere dos puntos cualesquiera en la misma línea horizontal o vertical de los dados. Calcula la distancia entre ellos. Con base en eso, forma los otros dos puntos. Ahora verifique si ambos puntos dados están presentes o no. Si es así, asegura que hay un cuadrado presente. Por lo tanto, aumente el conteo y continúe.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the count of
// squares parallel to both X and Y-axis
// from a given set of points
int countSquares(int* X, int* Y, int N)
{
    // Initialize result
    int count = 0;
 
    // Initialize a set to store points
    set<pair<int, int> > points;
 
    // Initialize a map to store the
    // points in the same vertical line
    map<int, vector<int> > vertical;
 
    // Store the points in a set
    for (int i = 0; i < N; i++) {
        points.insert({ X[i], Y[i] });
    }
 
    // Store the points in the same vertical line
    // i.e. with same X co-ordinates
    for (int i = 0; i < N; i++) {
        vertical[X[i]].push_back(Y[i]);
    }
 
    // Check for every two points
    // in the same vertical line
    for (auto line : vertical) {
        int X1 = line.first;
        vector<int> yList = line.second;
 
        for (int i = 0; i < yList.size(); i++) {
            int Y1 = yList[i];
            for (int j = i + 1; j < yList.size(); j++) {
                int Y2 = yList[j];
                int side = abs(Y1 - Y2);
                int X2 = X1 + side;
 
                // Check if other two point are present or not
                if (points.find({ X2, Y1 }) != points.end()
                and points.find({ X2, Y2 }) != points.end())
                    count++;
            }
        }
    }
 
    return count;
}
 
// Driver Code
int main()
{
    int X[] = { 0, 2, 0, 2 }, Y[] = { 0, 2, 2, 0 };
 
    int N = sizeof(X) / sizeof(X[0]);
 
    cout << countSquares(X, Y, N);
 
    return 0;
}

# Python3 implementation of the approach
 
# Function that returns the count of
# squares parallel to both X and Y-axis
# from a given set of points
def countSquares(X,  Y, N) :
 
    # Initialize result
    count = 0;
 
    # Initialize a set to store points
    points = [];
 
    # Initialize a map to store the
    # points in the same vertical line
    vertical = dict.fromkeys(X, None);
 
    # Store the points in a set
    for i in range(N) :
        points.append((X[i], Y[i]));
 
    # Store the points in the same vertical line
    # i.e. with same X co-ordinates
    for i in range(N) :
        if vertical[X[i]] is None :
            vertical[X[i]] = [Y[i]];
        else :
            vertical[X[i]].append(Y[i]);
 
    # Check for every two points
    # in the same vertical line
    for line in vertical :
        X1 = line;
        yList = vertical[line];
 
        for i in range(len(yList)) :
            Y1 = yList[i];
            for j in range(i + 1, len(yList)) :
                Y2 = yList[j];
                side = abs(Y1 - Y2);
                X2 = X1 + side;
 
                # Check if other two point are present or not
                if ( X2, Y1 ) in points and ( X2, Y2 ) in points :
                    count += 1;
 
    return count;
 
# Driver Code
if __name__ == "__main__" :
 
    X = [ 0, 2, 0, 2 ]; Y = [ 0, 2, 2, 0 ];
 
    N = len(X);
 
    print(countSquares(X, Y, N));
 
# This code is contributed by AnkitRai01

1

Complejidad Temporal: O(N ² ).

Espacio Auxiliar: O(N)