POJ2002 Squares(二維點哈希)

POJ2002 Squares(二維點哈希)

題意：

給定n個點 判斷這n個點可以構成多少正方形。

分析：

暴力枚舉一條邊的兩個端點，然後根據全等三角形可以求出可以構成正方形的另外兩個邊的端點，然後判斷這兩個兩存不存在。

因此首先要把所有的點哈希一下，然後依次暴力枚舉，因此四條邊都統計了一次 因此最後要除4.

代碼如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int mod = 10007;

const int maxn = 1010;

struct nod
{
    int x,y;
};

inline int read()//輸入外掛
{
    char ch=getchar();
    int x=0,f=1;
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

struct hashmap
{
    nod a[maxn];
    int head[mod],next[maxn],cnt;
    void init()
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(next,0,sizeof(next));
    }
    bool find(nod val)
    {
        int tmp = (val.x*val.x+val.y*val.y)%mod;
        for(int i=head[tmp]; i!=-1; i=next[i])
            if(a[i].x==val.x&&a[i].y==val.y)
                return true;
        return false;
    }
    void add(nod val)
    {
        int tmp = (val.x*val.x+val.y*val.y)%mod;
        for(int i=head[tmp]; i!=-1; i=next[i])
            if(a[i].x==val.x&&a[i].y==val.y)
                return;
        a[cnt]=val;
        next[cnt]=head[tmp];
        head[tmp]=cnt++;
    }
} h;

nod p[maxn];

int main()
{
    int n;
    while(~scanf(%d,&n))
    {
        if(n==0) break;
        h.init();
        for(int i=0; i>= 2;
        printf(%d
,ans);
    }
    return 0;
}