poj 2002 Squares(매거진+점hash)

Squares
Time Limit: 3500MS
 
Memory Limit: 65536K
Total Submissions: 12372
 
Accepted: 4535
Description
A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property. 
So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates. 
Input
The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.
Output
For each test case, print on a line the number of squares one can form from the given stars.
Sample Input

4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0

Sample Output

1
6
1

Source
Rocky Mountain 2004
제목:http://poj.org/problem?id=2002
제목: n개 점을 줄게, n개 점에서 4개의 점을 골라서 서로 다른 정사각형을 구성하는 개수를 물어봐.
분석: 가장 쉽게 떠오르는 방법은 두 개의 점을 하나하나 열거하는 것이다. 그러면 다른 두 개의 점은 구할 수 있다. 구한 후에 이 두 개의 점이 존재하는지 아닌지를 판단하고 존재는 +1이다. 구체적인 판단은 모든 점hash만 내리면 된다.
코드:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mm=1111;
const int mod=100007;
struct point
{
    int x,y;
}g[mm];
struct hashTable
{
    int h[mod],p[mod],size;
    point s[mod];
    int hash(int x,int y)
    {
        return ((x*131+y+mod)&0x7FFFFFFF)%mod;
    }
    void insert(int x,int y)
    {
        int i,id=hash(x,y);
        for(i=h[id];i>=0;i=p[i])
            if(s[i].x==x&&s[i].y==y)return;
        s[size].x=x,s[size].y=y;
        p[size]=h[id],h[id]=size++;
    }
    int find(int x,int y)
    {
        int i,id=hash(x,y);
        for(i=h[id];i>0;i=p[i])
            if(s[i].x==x&&s[i].y==y)return i;
        return 0;
    }
    void clear()
    {
        size=1;
        memset(h,-1,sizeof(h));
    }
}ht;
bool check(point P,point Q)
{
    int add1=P.y-Q.y,add2=Q.x-P.x;
    return ht.find(P.x+add1,P.y+add2)&&ht.find(Q.x+add1,Q.y+add2);
}
int main()
{
    int i,j,n,ans;
    while(scanf("%d",&n),n)
    {
        ht.clear();
        for(i=0;i<n;++i)
        {
            scanf("%d%d",&g[i].x,&g[i].y);
            ht.insert(g[i].x,g[i].y);
        }
        for(ans=i=0;i<n;++i)
            for(j=0;j<n;++j)
                if(i!=j&&check(g[i],g[j]))++ans;
        printf("%d
",ans/4);
    }
    return 0;
}