PKU 2002 Squares

http://poj.org/problem?id=2002
n個の点が与えられるので、4つ選んでできる正方形の個数を求めろというような問題。

O(n^2)でやりました。
ハッシュを使わないと厳しかったです。定数倍ゲー？

int x[1000],y[1000];

typedef struct _node{
  int x,y;
  _node* next;
}node;

const int hashMod=10003;

node ent[10000];
int sz;
node* hash[hashMod];

void insert(int x,int y){
  int ha=((x*37+y)%hashMod+hashMod)%hashMod;

  node* p=ent+sz++;
  p->next=hash[ha];
  p->x=x;
  p->y=y;
  hash[ha]=p;
}

bool count(int x,int y){
  int ha=((x*37+y)%hashMod+hashMod)%hashMod;
  for(node* p=hash[ha];p;p=p->next)
    if(p->x==x && p->y==y)return true;
  return false;
}

main(){
  int n;
  while(cin>>n,n){
    memset(hash,0,sizeof(hash));
    int sz=0;
    rep(i,n){
      scanf("%d%d",x+i,y+i);
      insert(x[i],y[i]);
    }
    int ans=0;
    rep(i,n){
      rep(j,n){
        if(i==j)continue;
        if(count(x[i]-(y[j]-y[i]),y[i]+x[j]-x[i]) &&
           count(x[j]-(y[j]-y[i]),y[j]+x[j]-x[i]))++ans;
        if(count(x[i]+(y[j]-y[i]),y[i]-(x[j]-x[i])) &&
           count(x[j]+(y[j]-y[i]),y[j]-(x[j]-x[i])))++ans;        
      }
    }
    cout<<(ans>>3)<<endl;
  }
}