Intentaré darte un algoritmo que, con suerte, podrías convertir en código C real. Un enfoque de fuerza bruta podría ser hacer esto:

1. Para cada punto de su conjunto, elija otro punto del conjunto.
2. Con base en la línea resultante, determine cuál sería la siguiente línea perpendicular en el cuadrado y verifique si existe un punto en el conjunto que coincida con lo que se necesitaría.
3. Si se encuentra este tercer punto (y, por lo tanto, el segundo lado), repita el paso 2 para el tercer lado del cuadrado.
4. Finalmente, si se encuentran tres puntos válidos, vea si el tercer punto se conecta apropiadamente con el punto original. Si es así, entonces tienes una coincidencia.
5. Si durante alguno de estos pasos hay una falla, entonces descartar el primer punto como candidato y volver al paso 1, eligiendo otro punto. Una vez que haya iterado sobre todos los puntos, habrá encontrado un cuadrado o habrá determinado que no existe ninguno.

Actualización y mejora:

1. Para cada punto del conjunto, compárelo con todos los demás puntos del conjunto buscando dos diagonales perpendiculares a otros puntos. Si lo encuentra, almacene los identificadores de los dos puntos a los que se conecta. Si no lo encuentra, descarte permanentemente este punto de su conjunto. Este paso será O(N^2) pero no veo forma de evitarlo.

2. A continuación, itere sobre los puntos "elegidos" (es decir, aquellos que tienen uno o más medios cuadrados), y verifique si los puntos a los que se conectan también se conectan de nuevo a otro punto elegido. Si es así, entonces has encontrado un cuadrado. El truco aquí es que no haces más cálculos aquí. Simplemente itera sobre el estado que ya tiene, lo que debería ser mucho más rápido que los cálculos en el primer paso.

Este enfoque supera al método de fuerza bruta porque solo tiene que calcular medios cuadrados. Calcular la fuerza bruta de los cuadrados es un asunto O(N^4) . Este enfoque es O(N^2) , pero en la práctica probablemente sería más rápido ya que el conjunto de puntos se reduciría a medida que avanza el algoritmo.

Dados dos puntos de un cuadrado, solo se pueden construir 3 tipos de cuadrados como muestra la siguiente imagen. Y para cada caso, podemos simplemente calcular las coordenadas de los otros dos puntos. Podemos verificar si dichos puntos existen usando un mapa o una tabla de banderas simple (bool exist[MAX_X][MAX_Y]) y satisfacer la "regla del mismo número" o no.

Así que enumere todos los casos de N * N, y cada uno marque los 3 tipos. La complejidad de tiempo general es O (N ^ 2 * logN) usando el mapa STL de C ++ u O (N ^ 2) usando la tabla de banderas o STL unordered_map de C ++.

Primero, algo de terminología: la cuadrícula/red se ejecuta horizontalmente "x" de izquierda a derecha 1..N y verticalmente "y" de arriba hacia abajo. Los cuadrados a hallar tienen vértices (esquinas) que numeramos en el sentido de las agujas del reloj 1..4. La primera de esas esquinas, que llamaremos TopLeft, es la que tiene el valor vertical (y) más bajo; si hay dos (un cuadrilátero no rotado) es el que tiene el valor horizontal (x) más bajo.

Algoritmo: escanee todos los puntos e intente construir un cuadrilátero con el punto dado como vértice #1, es decir, TopLeft. Esto da como resultado el siguiente pseudocódigo:

 // for each TopLeft candidate... for x1 = 1 to N-1 // TopLeft can never have x=N for y1 = 1 to N-1 // TopLeft van never have y=N // scan vertex #2 candidates... for x2 = x1+1 to N // #2 is always strictly to the right of #1 for y2 = y1 to N // #2 is never above #1 // resulting #3 coordinates x3 = x2 - (y2 - y1) if x3 < 1 then exit 'for y2' // all next y2 will also yield x3<1 y3 = y2 + (x2 - x1) if y3 > N then exit 'for y2' // all next y2 will also yield y3>N // resulting #4 x4 = x1 - (y2 - y1) if x4 < 1 then exit 'for y2' // all next y2 will also yield x4<1 y4 = y1 + (x2 - x1) if y4 > N then exit 'for x2' // all next x2 will also yield y4>N // colors ok? if grid(x1,y1)==grid(x2,y2) && grid(x1,y1)==grid(x3,y3) && grid(x1,y1)==grid(x4,y4) then // FOUND! count+=1 endif next y2 next x2 next y1 next x1