poj 2002 Squares【HASH】POJ最快

先排序，然后枚举任意两点(x1,y1)(x2,y2)，则如果存在点(x1+y1-y2,y1-x1+x2)(x2+y1-y2,y2-x1+x2)则它们能构成一个正方形

157MS

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
struct node
{
    int a,b,c;
}b[10000];

#define hash(x) ((x)&131071)
int a[141000];
void init(){
    memset(a,255,sizeof(a));
}
int ins(int x){
    int z=hash(x);
    while(a[z]!=-1&&a[z]!=x) z=hash(z+1);
    if(a[z]==-1) a[z]=x;
    return z;
}
int get(int x)
{
    int z=hash(x);
    while(a[z]!=-1&&a[z]!=x) z=hash(z+1);
    if(a[z]==-1) return -1;
    return z;
}
void read(int &d)
{
    char ch;bool flag=0;
    while(ch=getchar(),(ch>57||ch<48)&&ch!=45);
    ch==45?flag=1,d=0:d=ch-48;
    while(ch=getchar(),ch<=57&&ch>=48) d=d*10+ch-48;
    if(flag) d=-d;
}
bool cmp(node a,node b){
    return a.a==b.a?a.b<b.b:a.a<b.a;
}
int main()
{
    int n;
    while(read(n),n)
    {
        int ans=0;
        init();
        for(int i=0;i<n;i++)
        {
            read(b[i].a);read(b[i].b);
            b[i].a+=20500,b[i].b+=20500;
            b[i].c=b[i].a*41000+b[i].b;
            ins(b[i].c);
        }
        int x3,y3,x4,y4;
        sort(b,b+n,cmp);
        for(int i=0;i<n;i++)
        {
            int &x1=b[i].a,&y1=b[i].b;
            for(int j=i+1;j<n;j++)
            {
                int &x2=b[j].a,&y2=b[j].b;
                x3=x1+y1-y2,y3=y1+x2-x1;
                x4=x2+y1-y2,y4=y2+x2-x1;
                if(get(x3*41000+y3)==-1||get(x4*41000+y4)==-1) continue;
                ans++;
            }
        }
        printf("%d\n",ans/2);
    }
    return 0;
}

((x<<9)^y)&p p=65535或131071 157MS

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define hash(x) ((x)&131071)
int a[140000][2];
pair<int,int>b[10000];
int main()
{
    int n,ph;
    int x,y,dx,dy;
    while(scanf("%d",&n)&&n)
    {
        int ans=0;
        memset(a,255,sizeof(a));
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            x+=30000;y+=30000;
            b[i].first=x,b[i].second=y;
            ph=hash((x<<9)^y);
            while(a[ph][0]!=-1) ph=hash(ph+1);
            a[ph][0]=x,a[ph][1]=y;
        }
        sort(b,b+n);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                dx=b[j].first-b[i].first;
                dy=b[i].second-b[j].second;
                x=b[i].first+dy;
                y=b[i].second+dx;
                ph=hash((x<<9)^y);
                while(a[ph][0]!=-1&&!(a[ph][0]==x&&a[ph][1]==y)) ph=hash(ph+1);
                if(a[ph][0]==-1) continue;
                x=b[j].first+dy;
                y=b[j].second+dx;
                ph=hash((x<<9)^y);
                while(a[ph][0]!=-1&&!(a[ph][0]==x&&a[ph][1]==y)) ph=hash(ph+1);
                if(a[ph][0]==-1) continue;
                ans++;
            }
        printf("%d\n",ans/2);
    }
    return 0;
}