POJ - 2002 Squares解题报告

题目大意:给你一个二维平面上面的n（1000）个点的坐标（每个点坐标都不超过20000），让你找出有多少个正方形。给了三秒半····思路：还是先看一眼暴力枚举，4个点的所有可能组合为n^4肯定超时了。枚举每两个点的组合O(n^2)，然后看是否存在可以和他们组成正方形的点。即该位置上是否有点（用哈希表可以将查找过程时间复杂度降为O(1)。

这个哈希真是猛，只是要根据经验找个合适的哈希函数，一定要让哈希函数的值分布均匀，不然的话，和就相当于还是在枚举。这道题原本MOD为1000的时候3438ms险过。MOD改为10000之后，速度瞬间变快只需2469ms用空间换时间很划算。程序跑快快~

#include<iostream>#include<string.h>#include<stdio.h>#define N 1050#define MOD 10000using namespace std;int n;struct point{	int x;int y;}poi[N];int hash[MOD+10]={0};int next[MOD+10]={0};void input(){	for(int i=1;i<=n;i++)	{		scanf("%d%d",&poi[i].x,&poi[i].y);		int x;		x=(poi[i].x*poi[i].x+poi[i].y*poi[i].y)%MOD+1;		next[i]=hash[x];		hash[x]=i;	}}bool find(point x){	int u=(x.x*x.x+x.y*x.y)%MOD+1;	u=hash[u];	while(u)	{		if(poi[u].x==x.x&&poi[u].y==x.y)return 1;		u=next[u];	}	return 0;}void init(){	memset(hash,0,sizeof(hash));	memset(next,0,sizeof(next));}int main(){	while(cin>>n)	{		if(n==0)break;		input();		int s=0;		for(int i=1;i<=n;i++)		{			for(int j=1;j<=n;j++)			{				if(i==j)continue;				int x=poi[i].x-poi[j].x;				int y=poi[i].y-poi[j].y;				point p,q;				p.x=poi[i].x-y;				p.y=poi[i].y+x;				q.x=poi[j].x-y;				q.y=poi[j].y+x;				if(find(p)&&find(q))s++;				p.x=poi[i].x+y;				p.y=poi[i].y-x;				q.x=poi[j].x+y;				q.y=poi[j].y-x;				if(find(p)&&find(q))s++;			}		}		s=s/8;		cout<<s<<endl;		init();	}	}