题目描述

给定n个点，求可以构成的正方形的个数

思路

枚举其中的2个点，然后用公式求出其他两个点，在hash中查出是否两个点都存在就可以了，最后答案因为是每一个点都找了一次，所以要除4
O(n^2)

#include 
#define M 999987
int h[M+1];
struct arr
{
    int x,y;
};
arr a[M];
int insert(int x,int y)
{
    int l=(x*50000+y);
    int i=l%M;
    if (l<0) i=-l%M;
    while (h[i]!=-5201314&&h[i]!=l) i=i%M+1;
    h[i]=l;
}
int find(int x,int y)
{
    int l=(x*50000+y);
    int i=l%M;
    if (l<0) i=-l%M;
    while (h[i]!=-5201314&&h[i]!=l) i=i%M+1;
    if (h[i]==l) return true;
    else return false;
}
int main()
{
    int n;
    scanf("%d",&n);
    while (n!=0)
    {
    for (int i=1;i<=M;i++)
    {
        h[i]=-5201314;
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        insert(a[i].x,a[i].y);
    }   
    int ans=0;

    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            int x1,x2,y1,y2;
            x1=a[i].x+(a[i].y-a[j].y);
            y1=a[i].y-(a[i].x-a[j].x);
            x2=a[j].x+(a[i].y-a[j].y);
            y2=a[j].y-(a[i].x-a[j].x);
            if (find(x1,y1)&&find(x2,y2)) ans++;
            x1=a[i].x-(a[i].y-a[j].y);
            y1=a[i].y+(a[i].x-a[j].x);
            x2=a[j].x-(a[i].y-a[j].y);
            y2=a[j].y+(a[i].x-a[j].x);
            if (find(x1,y1)&&find(x2,y2)) ans++;
        }
    }
    ans=ans>>2;
    printf("%d\n",ans);
    scanf("%d",&n);
    }   
}