poj3432CountSquares

给你n个点,求这些点中可以构成多少个正方形.(顶点相同的算同一个)

基本做法

把所有点都用hash存起来,然后枚举两个点,算出另外的两个点,如果hash中能找到,则 可以构成一个正方形.

//bnu3551 poj3432
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define PRE  9949 
#define CH (pp[k][0]*pp[k][0]%PRE+pp[k][1]*pp[k][1]%PRE)%PRE
//用链地址解决冲突
struct node
{
    int k;
    struct node *next;
};
node* myhash[PRE+10];
int pp[2005][2];
//创建hash表
void creat(int k)
{
    int key=CH;
    if(!myhash[key])
    {
        node *p=new node;
        p->k=k;
        p->next=NULL;
        myhash[key]=p;
        return ;
    }
    node *p=myhash[key];
    while(p->next)
        p=p->next;
    p->next=new node;
    p->next->k=k;
    p->next->next=NULL;
}
//查找
bool findkey(int a,int b)
{
    int key=(a*a%PRE+b*b%PRE)%PRE;
    if(myhash[key])
    {
        node *p=myhash[key];
        while(p)
        {
            if(pp[p->k][0]==a &&pp[p->k][1]==b)
                return true;
            p=p->next;
        }
    }
    return false;
}
int main()
{
    int n,a,b,i,j,ca=0;
    int a1,a2,b1,b2;
    while(cin>>n&& n)
    {
        int ans=0;
        //ca++;
        for(i=0;i<PRE+1;i++)
            myhash[i]=NULL;
        for(i=0;i<n;i++)
        {
            cin>>pp[i][0]>>pp[i][1];
            creat(i);
        }
        for(i=0;i<n-1;i++)
        {
            for(j=i+1;j<n;j++)
            {
                a1=pp[i][0]+(pp[i][1]-pp[j][1]);
                b1=pp[i][1]-(pp[i][0]-pp[j][0]);
                a2=pp[j][0]+(pp[i][1]-pp[j][1]);    
                b2=pp[j][1]-(pp[i][0]-pp[j][0]);
                if(findkey(a1,b1) && findkey(a2,b2))
                    ans++;
                a1=pp[i][0]-(pp[i][1]-pp[j][1]);
                b1=pp[i][1]+(pp[i][0]-pp[j][0]);
                a2=pp[j][0]-(pp[i][1]-pp[j][1]);    
                b2=pp[j][1]+(pp[i][0]-pp[j][0]);
                if(findkey(a1,b1) && findkey(a2,b2))
                    ans++;
            }
        }
        cout<<ans/4<<endl;//存在重复情况,一个正方形被按不同的方式找了四次
    }
}