Efficient way to Find if points form a Square. Calculation C++

Question

I'm new here. I'm solving a problem to check if N points (x,y) form a square. The final output is the number of squares the points can form + the biggest area (one of the squares). Input like this:

6
1 1
1 2
1 3
2 3
2 2
2 1

Output:

2 -> (2 Squares were formed)
1 -> (1 was the biggest area)

So I'm reading the x and y like this:

cin >> n;
    for(int i=0;i<n;i++)
    {cin >> coordenadas[i].x >> coordenadas[i].y;concat[i]=coordenadas[i].y * 100000 + coordenadas[i].x;}
    sort (concat, concat+n);
    for(int i=0;i<n;i++)
    {
        A.x=coordenadas[i].x;A.y=coordenadas[i].y;
        for(int ii=M;ii<n;ii++)
        {
            B.x=coordenadas[ii].x;
            B.y=coordenadas[ii].y;
            ...
            calculo();
            if(mArea<area)
            mArea=area;
        }
        M+=1;
    }

In the next function, i'm trying to calculate a x and y var to get the values like this -> https://i.sstatic.net/Uqtau.png

But i'm not sure about my calculation.

And my calculo function:

void calculo()
{
    int x=0,y=0;
    if(A.x==B.x)
    {
        x=abs(B.y-A.y);
        area=x*x;
        R1.c1=(B.y) * 100000 + (A.x + x);
        R1.c2=(B.y) * 100000 + (A.x - x);
        if (binary_search (concat, concat+n, R1.c1))
        if (binary_search (concat, concat+n, R1.c2))
        quadrados+=1;
        else
        area=0;
    }
    else
    {
        x=abs(B.y-A.y);
        y=abs(B.x-A.x);
        area=sqrt(x*x+y*y)*sqrt(x*x+y*y);
        R1.c1=(B.y + y) * 100000 + (B.x - x);
        R1.c2=(A.y + y) * 100000 + (A.x - x);
        if (binary_search (concat, concat+n, R1.c1))
        if (binary_search (concat, concat+n, R1.c2))
        quadrados+=1;
        else
        area=0;
    }
}

What I'm doing is, pick 2 unique points and calculate the possible other two points that form a square. then I "concat" them into a unique integer (eg. (B.y + y) * 100000 + (B.x - x) wich means -> y * 100000 +x) then i look for them with a binary search, if they were found i increment the n_square var.

The problem is, I'm not sure if the calculation is ok, and I need a hand with this. I know that there is a way to calculate with bitset but I'm not an expert so i can't use bitset. I'm trying to get a O(N^2 * log(V)) solution. Give me some tips

################### NEW EDIT AFTER SOME COMMENTS -> ###################

NEW Input (Comment)

9
5 3
1 4
1 3
1 2
2 1
2 3
3 4
3 2
4 2

Output:

6 (Number of Squares)
0 (Its Area-> I'm not calculating yet)

Expected Output

3
5 (Area)

New Code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct c{

    int x,y;

}A,B,C,D,coordenadas[3001];

int quadrados=0,n=0;
long int area;
long int concat[3001];

int dist2 (c A,c B) {
  int x = A.x - B.x;
  int y = A.y - B.y;
  return x*x + y*y;
}



void calculo()
{
    int d = dist2(A, B);
    const int x = B.x - A.x;
    const int y = B.y - A.y;
    C.x = A.x - y;
    C.y = A.y + x;
    D.x = B.x - y;
    D.y = B.y + x;
    d = dist2(A, B);
    if (dist2(A, C) == d && 2*d == dist2(B, C))
    if (binary_search (concat, concat+n, C.y * 100000 + C.x))
    if (dist2(B, D) == d && dist2(C, D) == d)
    if (binary_search (concat, concat+n, D.y * 100000 + D.x))
    {
        quadrados+=1;
    }

}

int main() {

    int M=1,mArea=0;
    cin >> n;
    for(int i=0;i<n;i++)
    {cin >> coordenadas[i].x >> coordenadas[i].y;concat[i]=coordenadas[i].y * 100000 + coordenadas[i].x;}
    sort (concat, concat+n);
    for(int i=0;i<n;i++)
    {
        A.x=coordenadas[i].x;
        A.y=coordenadas[i].y;
        for(int ii=M;ii<n;ii++)
        {
            B.x=coordenadas[ii].x;
            B.y=coordenadas[ii].y;
            calculo();
            if(mArea<area)
            mArea=area;
        }
        M+=1;
    }

    if(quadrados==0)
    cout << quadrados << endl;
    else
    cout << quadrados << endl << mArea << endl;
    return 0;
}

Answer 1

I'll assume that all coordinates are integers and your chosen type can fit twice the square of the largest coordinate (800 million, in your case -- not hard). The latter assumption can be dispensed with, if needed, but the former isn't so easy since you'd otherwise have to decide how to handle rounding.

The basic idea is to loop through each point A and each point B appearing later in the list than A. Compute

int dist2 (A, B) {
  int x = A.x - B.x;
  int y = A.y - B.y;
  return x*x + y*y;
}

int d = dist2(A, B);

so that d is the squared distance between A and B. Now define

c C1, C2, D;
C1.x = 2*A.x - B.y;
C1.y = B.x;
C2.x = B.y;
C2.y = 2*A.y - B.x;

and check if C1 (resp., C2) is on the list following B. If so, call it C and check if

dist2(B, D) == d && dist2(C, D) == d

If so, ABCD is a square. If you have n elements in total the first two loops happen n(n-1)/2 times and each pair causes 2 or 3 lookups, showing that the algorithm runs in time O(n^2 log n).

Edit: An earlier version also gave a simpler algorithm which ran in time O(n^3). Its existence caused confusion so I removed it and made the other algorithm more explicit.

Answer 2

From your picture:

const int x = B.x - A.x;
const int y = B.y - A.y;
C.x = A.x - y;
C.y = A.y + x;
D.x = B.x - y;
D.y = B.y + x;

then

area = x * x + y * y;