c++ - 查找点是否形成正方形的有效方法。计算 C++

Question

我是新来的。我正在解决一个问题来检查 N 个点 (x,y) 是否形成一个正方形。最后的输出是点能组成的方格数+最大面积(其中一个方格)。 像这样输入:

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

输出:

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

所以我是这样读 x 和 y 的:

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;
    }

在下一个函数中，我尝试计算 x 和 y 变量以获得这样的值 -> http://i.stack.imgur.com/Uqtau.png

但我不确定我的计算。

还有我的计算函数:

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;
    }
}

我正在做的是，选择 2 个独特的点并计算可能形成正方形的其他两个点。然后我将它们“连接”成一个唯一的整数(例如 (B.y + y) * 100000 + (B.x - x) wich means -> y * 100000 +x)然后我用二进制搜索寻找它们，如果它们被发现我增加 n_square 变量。

问题是，我不确定计算是否正确，我需要帮忙。我知道有一种方法可以用 bitset 进行计算，但我不是专家，所以我不能使用 bitset。我正在尝试获得 O(N^2 * log(V)) 解决方案。给我一些建议

################### 一些评论后的新编辑 -> ############### ####

新输入(评论)

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

输出:

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

预期输出

3
5 (Area)

新代码:

#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

来自你的照片:

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;

然后

area = x * x + y * y;